Merge Sort (JavaScript)

Sorting data is a notoriously slow process. In real life, if you’re given a list of 10 numbers and asked to sort it, you’ll probably first look through all the numbers for the lowest one, then you’ll look through them again for the next lowest, and you’ll repeat this process until you’ve covered everything.

A lot of the time in code, it’s a similar story. You’ll loop through the numbers, and then for each number, you’ll compare it with all of the other numbers. Slow and inefficient.

Enter “merge sort”, a concept where we split our to-be-sorted data in two, sort each half, and then merge those two halves together.

Now, that probably doesn’t sound terribly intuitive at first. After all, we’re still having to sort each half, so how is that any easier? Well, the key differentiator is that we actually keep splitting our data in half until we have just 2 elements, at which point, we simply compare them to each other in order to sort them.

So let’s imagine we now have two sorted halves. Well, rather than loop through every possible number like we originally had to, we now only ever need to compare the lowest number of each half. For example, if we have sorted arrays of [1, 4, 6, 7] and [2, 3, 5, 8], we can merge them together by saying “Is 1 smaller than 2? Yes, so use 1. Is 4 smaller than 2? No, so use 2. Is 4 smaller than 3? No, so use 3” until we eventually end up with a sorted, merged array of numbers.

Some code

Let’s look at a practical example of merge sort code. In this fairly classic implementation (which has been drawn out a little to aid readability), we recursively split our array in half, until we can no longer split it (only a single element remains). Once we reach that point, we begin backtracking up our recursive calls, and at each stage we then merge the split halves together, until we’re all the way back at the top, with a merged, sorted version of our original array.

Let’s run through this flow with an array of [1, 5, 3, 8, 4, 2, 9, 6].

First, we’ll split it in half, to get our left-hand side of [1, 5, 3, 8]. Now as that’s still too many elements, we’ll split it again to [1, 5], and again to get [1] and [5]. Now that we’ve sufficiently split down our first contenders, let’s compare them. We see that 1 is less than 5, so we return the merged and sorted array of [1, 5]. Similarly, we also compare the next pair of 3 and 8, and return [3, 8], so it’s time for our first merge.

We’ll declare a new array, and then compare each side’s first values; 1 and 3. We know 1 is lower, so we’ll remove 1 from the left-hand side and put it into the new array. So at this point, we have a left-hand side of [5] , a right-hand side of [3, 8] and a new array of [1]. Comparing the next set of values (5 and 3), we can see that 3 is lower, so we remove that and add it to the new array. We now have a left array containing only 5, a right array containing only 8, and a new array of [1, 3]. So we now compare 5 and 8, see that 5 is lower, and so remove that and put it on the new array to give us [1, 3, 5].

At this point, because our left array is empty, we can save time by simply appending what remains of our right array onto the new array, as we know those numbers will be higher than all of the existing numbers in the new array. By doing this, we add our last remaining number of 8 to our new array, to give us [1, 3, 5, 8], a merged and sorted array.

As the call stack moves upward, we’ll then repeat this process with the right-hand side, giving us a sorted array of [2, 4, 6, 9], and then merge-sort the two arrays together, using the aforementioned method, to get [1, 2, 3, 4, 5, 6, 8, 9], a merged and sorted version of the original array.

Closing out

Merge-sorting requires a number of key concepts to be understood before you can fully understand the approach, the most important of which is recursion. But once you have a good understanding of recursion, the rest should start to make sense.

If however you’d like a little more help, I found this video from mycodeschool around the theory of merge-sorting to be a really helpful one, especially as it visualises how the data is manipulated at each individual stage.