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.