Sorting Algorithms: Merge Sort
This is part of a series of blog posts where I discuss JavaScript Sorting algorithms. I initially started this journey discussing Bubble Sort, and found myself wanting to discuss the entire array of sorting algorithms. In this blog post we will be discussing one of the first sorting algorithms I started learning, Merge Sort. I’ve heard some people say that this is considered an intermediate sorting algorithm, and I agree because of the steps taken to implement this algorithm. I hope this can be a good reference and refresher for those familiar with Merge sort. And for those new to merge sort, I hope this can be used as a quick “how-to-implement” guide.
Merge Sort is an algorithm that works recursively. Let’s pause there and go straight into what happens in merge sort. Long story short, we take in an array (unsorted) and we break it into pieces, and then merge them back together and then output a sorted array. It sounds like magic and also like a long drawn out mess of an algorithm, but there is beauty and order to this seemingly mad solution to a problem. How does this work? Well let’s break it down one step at a time.
The Merge Part to Start
To begin, let’s go over some of the pre requisites of what is needed in order to implement merge sort.First we want to start by implementing a function that merges two sorted arrays to be our helper. The function will do this: it will take two arrays (*Note: which we will get from our original unsorted array), it will scan both arrays and check each and every index, pushing the lower value into a new array. Once we’ve gone through all values, and pushed them into the new array, we will return this new and now sorted array. Let’s create that function.
function merge(array1, array2) {
//results is an empty array
let results = [];
let i = 0
let j = 0
while( i < array1.length && j < array2.length){
// We will compare the indexed items in each array, pushing the lower values into results. In the event that one of the arrays is larger, we create a while loop that says while either i or j is less then array1 or array2 respectively, we will continue pushing their elements and incrementing the value of i or j.
if(array2[j] > array1[i]){
results.push(array1[i])
i++
} else {
results.push(array2[j])
j++
}
while(i < array1.length) {
results.push(array1[i])
i++
}
while(j < array2.length) {
results.push(array2[j])
j++
}
}
return results;
}Let’s break down the code above. We are creating a function called merge that takes in two arguments, array1 and array2. Within it, we are:
- Declaring three variables:
1) results which is an empty array,
2) i which represents the index of array1 and we are setting it’s initial value to 0, and
3) j which represents the index of array2 and has an initial value of 0 as well.
- Next we create a loop that says, while i and j are both less than the lengths of array1 and array2 respectively, we will carry out the following conditions:
- Until we have pushed all values from array1, and array2, compare the elements of array1 and array2, so that if array1[i] is less than array2[j], or vice versa, we will push the lower value into the results array.
- In the last two while conditions, if we exhaust one array before the other, as long as i or j is less then their corresponding array lengths, we will continue pushing the remaining elements of the array that still contains elements into the results array.
- Then we will return results aka the sorted array.
merge ([1, 50], [2, 8, 100])
// results = [], j = 0, i = 0
[1, 50] [2, 8, 100]
// arr2[j] > arr1[i] // 2 > 1 ? TRUE
// results = [ 1 ], j = 0, i = 1
// arr2[j] > arr1[i] // 2 > 50 ? FALSE
// results = [ 1, 2 ], j = 1, i = 1
{repeats}
// arr2[j] > arr1[i] // 8 > 50 ? FALSE
// arr2[j] > arr1[i] // 100 > 50 ? TRUE
// j < arr2.length // 2 < arr2.length ? TRUE
// => results = [ 1, 2, 8, 50, 100 ]The Sorting Part for the Finale
Let’s go over the sorting part to Merge Sort. The sorting portion of the algorithm will work recursively. Remember that we are starting with one unsorted array. To get our desired output, this algorithm works by breaking our array into little pieces. Put simply, we want to create individual arrays for each element in our entire array, before putting it back together. You may be wondering where is the sense in that.
Let’s think of it this way:
Imagine you start with an array of eight unsorted items.
[3, 1, 6, 5, 2, 8, 7, 4] (unsorted)
Let’s break the array into two so that we now have two arrays of four unsorted values.
[3, 1, 6, 5] [2, 8, 7, 4] (unsorted)
And then repeat this again.
So now we have four unsorted arrays of two values…
[3, 1] [6, 5] [2, 8] [7, 4] (unsorted)
and then finally eight arrays with one value each.
[3][1][6][5][2][8][7][4] (sorted)
The benefit of breaking down an unsorted array to multiple arrays with one individual element is that, when there is only one element in an array, that array is already sorted, making it easy to merge, and ultimately, sort our arrays. Further, the steps needed to sort an array are far fewer, even though the written code looks like it’s doing a lot more than our previous sorting algorithms. In truth, the algorithm is running in a big O of n * log n which is great. In our example of the unsorted array, we have 8 items in the array which represents n. As we break down the array, we are implementing a binary type of logic, which is to say that it is the opposite of squaring a value. So in other words, how many times can an array with eight numbers be halved before we get to one item per array. 8 is halved 3 times before it gets to 1.
8/2 => 4/2 => 2/2 => 1
To Implement Sort with Merge
Again, we want to split our array into two halves until we have arrays that are empty or have one element with array.slice. We want to do this implementing a recursion so that we are slicing our array into haves until we no longer can. And then once we’ve reached our base case, which is the point when we can no longer slice, because the values of each index are 0 or 1, we will then begin merging the arrays, and sorting them simultaneously with our merge function.
function mergeSort(array){
if(array.length <= 1) return array;
let midPoint = Math.floor(array.length/2)
let left = mergeSort(array.slice(0, mid));
let right = mergeSort(array.slice(mid));
return merge(left, right);
} Final Break Down.
In the code above, we are breaking our array into halves. We start with a catch statement that if our array’s length is less than or equal to one, we will return the array. This will be the base for when we can no longer slice an array because it’s length is 0 or 1.
On the second line, we are creating a variable called midPoint that is equal to half of the value of the length of our array. Math.floor ensures that we round down to the nearest whole number. So if we are dividing 9 by 2, even though the technically the value would be 4.5 we round down to 4.
On the next lines, we are creating variables “left” and “right” and making a recursive call to mergeSort, where we are passing in the left and right half of the original array as arguments. Here we create a call stack of recursive functions, that when carried out will continue on to the final line of our mergeSort function, which will return a sorted array bit by bit leading to eventually return our final sorted array.
Again to reiterate, Merge Sort works by splitting an array into smaller arrays of 0 or 1 elements, then building up a newly sorted array. A divide and conquer approach. Splitting arrays recursively until we have single sub arrays, guarantees that single element arrays will be sorted and then can be merged back together.
[3, 1, 6, 5, 2, 8, 7, 4] (unsorted)
[3, 1, 6, 5,] [ 2, 8, 7, 4 ] (unsorted)
[3, 1] [6, 5] [2, 8] [7, 4] (unsorted)
[3][1][6][5][2][8][7][4] (sorted 0 index arrays)
[ 1, 3 ] [ 5, 6 ] [ 2, 8 ] [ 4, 7 ] (sorted arrays)
[ 1, 3, 5, 6 ] [ 2, 4, 7, 8 ] (sorted arrays)
[ 1, 2, 3, 4, 5, 6, 7, 8 ] ( sorted array )
