Merge Sort
In a previous article, I discussed the insertion sort algorithm and how to solve it. To remind how it is done, first we find the minimum number in the array. Once we find it, we delete it out of the original array and return it. The second function is then called to insert it into the new array and keep repeating the steps until we have a sorted array. I will link the article for you to read at the references section.
Merge sort is similar because we look at two arrays and determine the lower first number of both arrays. Whichever array has the lower first number, it is removed. After that, we call a new function to insert the lowest number into a new sorted array.
Let’s say we are given these two arrays
firstArray = [1, 2, 6, 7, 8]
secondArray = [3, 4, 5, 9, 10]. We see the first number for both arrays is 1 and 3, and the lower number is 1. That number is removed and the remaining arrays are
firstArray = [2, 6, 7, 8]
secondArray = [3, 4, 5, 9, 10].The sorted array is now
sort = [1]. Now, we see the first numbers of both arrays are 2 and 3; smaller number is 2, and updated arrays are now
firstArray = [6, 7, 8]
secondArray = [3, 4, 5, 9, 10]and the sorted array is now
sort = [1, 2].We keep repeating this until the final sorted array is
sort = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Now that we are done explaining the steps, let’s see how we can do that with code.
The first step is to grab the first number of both arrays and then we compare them. We start out by writing out
function findMinAndRemove(firstHalf, secondHalf){
let minfirstHalf = firstHalf[0]
let minsecondHalf = secondHalf[0]to grab the first number of both arrays., and then we utilize the if-else to compare both numbers and see that whichever is smaller will be removed from its array
if(minfirstHalf < minsecondHalf){
return firstHalf.shift()
}
else {
return secondHalf.shift()
}which will give the full code for this to be
function findMinAndRemove(firstHalf, secondHalf){
let minfirstHalf = firstHalf[0]
let minsecondHalf = secondHalf[0]
if(minfirstHalf < minsecondHalf){
return firstHalf.shift()
}
else {
return secondHalf.shift()
}
}. Don’t forget to include shift for each array because we will have an infinite loop for the second function. We are done with the first part.
The second part is to merge two arrays into one. We will be using a while loop just like what we did in the insertion sort algorithm. First step in this function is to declare an array called sort
function merge(firstHalf, secondHalf){
let sorted = []and we set the minimum to equal the function findMinAndRemove and insert the minimum number into sorted while both arrays have a length greater than zero
while(firstHalf.length != 0 && secondHalf.length != 0){
let currentMin = findMinAndRemove(firstHalf, secondHalf)
sorted.push(currentMin)
}
return sorted.concat(firstHalf).concat(secondHalf). What this will do is bring the two arrays together in a sorted manner, and I guess we can say we are done because the numbers are now sorted as we see in figure 1.
But we would be wrong because let’s make 8 negative and see the result in figure 2.
We see that -8 is still at the same spot as positive 8 when we look at figure 1. So what do we do now?
To fix this, we need to create a new function that calls the merge function which will call the findMinAndRemove function. We see that we check the first number of both arrays and determine the smaller integer and then call the second function to put them all together. So in the third function, we split the unsorted array into 2 halves
unsorted = [12, 10, 9, 14, 1, 3, 5, 11, 6, 15, 16, 13, -2, 4, 8, 7]
firstHalf = [12, 10, 9, 14, 1, 3, 5, 11]
secondHalf = [6, 15, 16, 13, -2, 4, 8, 7]and call the previous functions to sort them and present the final sorted array
[-2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]. For this third function, we shall call it mergeSort. The first step we must do is to split the array into 2 arrays of equal length so that we can invoke the findMinAndRemove function
function mergeSort(array){
let midpoint = array.length/2
let firstHalf = array.slice(0, midpoint)
let secondHalf = array.slice(midpoint, array.length). If the length of the array is less than 2, we simply return the array. There is nothing to sort. The else-statement becomes interesting because we would think that we can have
if(array.length < 2){
return array
}
else {
return merge(firstHalf, secondHalf)
}but we would be wrong as we see in figure 3.
So what can we do? One thing we can do is turn mergeSort into a recursive function. We know that mergeSort will combine split one array into two, sort it, and rejoin them back to one. In line 32, we simply replace
return merge(firstHalf, secondHalf)with
return merge(mergeSort(firstHalf), mergeSort(secondHalf)). With this, we can get the answer we are supposed to see in figure 4
We see the unsorted array
unsorted = [12, 10, 9, 14, 1, 3, 5, 11, 6, 15, 16, 13, -2, 4, 8, 7]is now
[-2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]. It works now. The full code is
function findMinAndRemove(firstHalf, secondHalf){
let minfirstHalf = firstHalf[0]
let minsecondHalf = secondHalf[0]
if(minfirstHalf < minsecondHalf){
return firstHalf.shift()
}
else {
return secondHalf.shift()
}
}function merge(firstHalf, secondHalf){
let sorted = []
while(firstHalf.length != 0 && secondHalf.length != 0){
let currentMin = findMinAndRemove(firstHalf, secondHalf)
sorted.push(currentMin)
}
return sorted.concat(firstHalf).concat(secondHalf)
}function mergeSort(array){
let midpoint = array.length/2
let firstHalf = array.slice(0, midpoint)
let secondHalf = array.slice(midpoint, array.length)
if(array.length < 2){
return array
}
else {
return merge(mergeSort(firstHalf), mergeSort(secondHalf))
}
}
I hope the explanation was clear. Let me know if it is not.
