In the flow

Lessons learnt from Merge Sort

2 min read

Alternatively: Well we could do it better.

· · ─ ·✶· ─ · ·

I was implementing merge sort from scratch. Now this is not the hardest algorithm to wrap your head around but the implementation might be bit tricky due to the recursions and have to integrate that with its unique merge feature.

I did the below for my recursive mergeSort function:

private List<Integer> mergeSort(List<Integer> nums) {
    if (nums.size() == 1) return nums;
    int mid = (int) ((nums.size() - 1) * 0.5);
    List<Integer> left = mergeSort(nums.subList(0, mid + 1));
    List<Integer> right = mergeSort(nums.subList(mid + 1, nums.size()));
 
    return this.merge(left, right);
}

This is perfectly fine code but can be improved in two ways:

  1. The base condition can be changed to if (nums.size() <= 1) return nums; to handle scenarios where nums = []

Note: Using == 1 is also fine because if nums = [] then we get an IndexOutOfBoundsException at subList() operation

  1. int mid = nums.size() / 2; is much more easier to read than whatever abomination I wrote before.

But using this means more changes to get left and right

Effectively,

int mid = n / 2;
left  = [0, mid)
right = [mid, n)

So in code we end up doing,

if (nums.size() <= 1) return nums;
int mid = nums.size() / 2 ;
List<Integer> left = mergeSort(nums.subList(0, mid));
List<Integer> right = mergeSort(nums.subList(mid, nums.size()));

And onto merge. Part of the code is :

while (i < left.size() && j < right.size()) {
    if (left.get(i) < right.get(j)) {
        merged.add(left.get(i));
        i++;
    } else {
        merged.add(right.get(j));
        j++;
    }
}

This isnt stable ie, if two elements are equal then after the sort operation they wont appear in their original order.

Eg, lets say we had [2a, 2b] which are equal but 2a appeared before 2b in the original array. Since they are equal, they dont satisfy the if condition and the right is picked up before left. This effectively switches the order.

Now agreed this doesnt matter for numbers but if we have something like,

(Alice, age=20)
(Bob,   age=20)
(Charlie, age=25)

And we’re sorting using age. Unstable sort would give

(Bob,20), (Alice,20), (Charlie,25)

So to fix this we just do,

if (left.get(i) <= right.get(j)) {
    ...
}

These all makes the code nicer and cleaner by just a little bit.

· · ─ ·✶· ─ · ·

Graph View