Basic Solutions to Sorting Algorithms: Merge Sort
This week, I will be tackling my third (and final) Sorting Algorithm: Merge Sort. Merge Sort is definitely a challenging problem, so if you are new to sorting algorithms I’d recommend checking out my guides to Bubble Sort and Selection Sort before you attempt to tackle Merge Sort.
A Quick Note on Recursion
I mentioned that I found Merge Sort to be a particularly difficult problem and that is primarily because the Merge Sort solution requires us to use recursion. A recursive algorithm, if you’re unfamiliar, is “an algorithm which calls itself with ‘smaller (or simpler)’ input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input”¹.
That definition might seem a bit confusing at the moment, but when we go over the implementation of this problem, hopefully the idea of recursion will make a bit more sense.
The Solution: The Merge Function
Our solution to Merge Sort actually requires us to write two functions that we will call MergeSort and Merge. We will start by writing out our implementation to Merge as it is, I think, much easier to understand and also necessary for our later implementation of MergeSort.
The purpose of merge function is to take two separate sorted arrays and merge them together into one sorted array. Merge will be called with two arguments, named left and right, which will refer to each one of these separate sorted arrays.
To get merge working, we will first create a new array to hold our final sorted algorithm. In my solution, I called this array “results”.
Next, we will write a conditional while statement. This while statement will first check to see if we still have elements in BOTH arrays and as long as that conditional statement is met, we will compare the first values in both arrays to see which value is smaller. The smaller value will then be pushed into our results array. Finally, we can use the built-in JavaScript method shift to remove the first element from whichever array contained the smaller element.
Before we get too lost in my slightly confusing explanation of this code, here’s how this while statement will look in practice:
while (left.length && right.length) {
if (left[0] < right[0]) {
results.push(left.shift())
} else {
results.push(right.shift())
}
}The final step to this first function in our Merge Sort solution is to take everything remaining in the array that still contains elements and put those elements into our results array. If you are a bit lost by that step, remember that our while loop will only run as long as BOTH arrays still contain elements. So, once one array is empty that will loop will cease running and thus we will have one array still containing elements that will need to deal with in order to fully merge our original two arrays.
To do this, we can make use of some useful ES6 syntax: the spread operator(…). The spread operator is incredibly useful and can help you do many things in JS, but for our purposes it allows to quickly combine multiple arrays (known as array concatenation).
Since we’ve now gone over each part of this function separately, here’s the merge function in its entirety:
function merge(left, right) {
let results = [] while (left.length && right.length) {
if (left[0] < right[0]) {
results.push(left.shift())
} else {
results.push(right.shift())
}
} return [...results, ...left, ...right]
}
The Solution: Uh-oh, it’s time for recursion
Now that we’ve addressed our merge function, it’s time to take a look at our recursive MergeSort function:
function mergeSort(arr) {
if (arr.length === 1) {
return arr
}
let center = Math.floor(arr.length / 2)
let left = arr.slice(0, center)
let right = arr.slice(center) return merge(mergeSort(left), mergeSort(right))}
***I don’t want to get too bogged down on the technicalities of some of the built-in Javascript methods we are using in this function, but if you are curious about the specifics of how they work, here are some links to documentation on the floor and slice methods***
The basic purpose of our mergeSort function is to take an input array and divide it as small as we possibly can, which in our case will be into single element pieces.
Thus, due to the recursive nature of mergeSort, our function will run until our original array is broken into arrays that contain only one element each as once the input array is small enough, we will reach our conditional if statement and stop running our function.
Upon reaching our if statement, we will return the input array (which at this point will just be an array containing a single element). That return value will then be passed to our merge function to be merged and sorted into our final results array.
Here’s a diagram that gives us a good overview of this entire process:
As you can see, we start at the top with our original input array (red). That array then gets passed to our mergeSort function (red), which will keep dividing arrays until the input arrays are only one element each (grey). Then, those single element arrays, will be passed to our merge function (green). This process will continue until every element in our original array has been merged into one final sorted array.
MergeSort is a very tricky problem and I’m certainly no expert, so if you’re still feeling lost, here are some links I found helpful in my own understanding of this problem. Also, I’ve said it before and I’ll say it again, but the best way to get better at solving algorithms is to practice! Good luck and happy coding!
