CODEX

Merge Sort: Broken Down Line by Line

Introduction

Most developers who are studying Algorithms for the first time may hit their first algorithmic wall with Merge Sort. Merge Sort is different from the more elementary sorting algorithms in that it requires both a helper function, and a good understanding of recursion. So in this tutorial I am going to give you a line by line analysis so that you can get a good grasp of one of the most common and essential sorting algorithms. Note: If you want to copy the code to follow along it is at the bottom.

What are we trying to accomplish with Merge Sort?

The answer to this question may seem obvious. Of course we are trying to create an algorithm that will sort an array. But the real question is how does Merge Sort get from an array of unordered numbers to a perfectly sorted array? Well it takes advantage of one simple fact in order to do so. That fact is that all arrays of one element or less are sorted. For example, if you had the array below and you wanted to make four sorted arrays. What would you do?

Well you would most likely take each number and put them in their own array. Merge Sort does the same thing, but it splits the array in half until it gets there like so:

Now we have four separate completely sorted arrays. What Merge Sort does is it takes these four sorted arrays, and merges them into one completely sorted array. Until we are left with something like this:

Writing the Merge Function

So now that you have a somewhat clear understanding of what Merge Sort intends to do with our unsorted array. We must now look at the first, and longest part of the algorithm. In order to compare our arrays, and put them together in the right order we will have to first figure out how to merge them.

The first thing we have to do is define a merge function that will take in two arrays, and merge them together. We’ll go through this function line by line so that you can understand the reasoning behind everything I am doing.

Lines 1 and 2: We first define an empty array that we will use as our result.

Lines 3–5: We create two counter variables that will help us iterate through our arrays separately.

Line 6: We define a while loop that will compare the items of each array, and push them to our result array in order. In this line we are doing this until our counter variables are equal to the length of both arrays.

Lines 7–15: We then compare the items in both arrays, and push them to our result array in the correct order. After which depending on which array the item came from we increment its respective counter variable.

You may think we are done with our merge function, but let’s say we had two arrays like this [1,2] [3,4,5,6,7,8]. Our result array would then only be [1,2], because our counter variable would have broken us out of the loop. So we have to create a way to push the elements of the second array into our result array.

Lines 16–25: We now wrap up our function by creating two while loops. Both of which look at each counter variable, and push the rest of the elements of the array that haven’t been completely iterated through into our result array.

The Merge Sort Function

Now that we have a way to merge things, we can now create the merge sort function. This function is only 5 lines, but each line is super important so I’ll be sure to break each one down for you.

Lines 1–2: In this first line we are establishing what is known in recursion as our base case. Since we are breaking down the array into single item arrays, we know to return them when they are at the most one item. If you recall from before, arrays of one item are always sorted.

Line 3: Now that we have our base case we need to establish a way to find the middle of our array so that we can start splitting it in half. We do that by dividing the length of our array by 2 and using Math.floor to round it down.

Line 4: Now here’s where things start to get tricky. I recommend copying the code and stepping through each recursive step. So as you know by now Merge Sort breaks the array down into single item arrays and then merges all those arrays into each other. Well here we are splitting the left side of the array until we get to single item arrays on the left side.

Line 5: We are doing the same thing as the last line, but for the right side.

Line 6: Now here is where everything comes together. The two lines before this one give us our single item arrays. And now we use our merge function to combine them. So let’s say we have 4 single item arrays. After calling merge we will have two sorted arrays, and then we will call merge again which will finally give us our sorted array. Note: This step is difficult, so I recommend going through it a few times to understand exactly what is happening.

The Code

function merge(arr1, arr2){
 let result = []
 let i = 0
 let j = 0
 
 while( i < arr1.length && j < arr2.length){
  if(arr2[j] > arr1[i]){
   result.push(arr1[i])
   i++
   } else {
   result.push(arr2[j])
   j++
   }
 }
 
 while(i < arr1.length){
   result.push(arr1[i])
   i++
  }
 while(j < arr2.length){
   result.push(arr2[j])
   j++
  }
 
 return result
}
function mergeSort(arr){
 if(arr.length <= 1) return arr;
 let mid = Math.floor(arr.length/2)
 let left = mergeSort(arr.slice(0, mid))
 let right = mergeSort(arr.slice(mid))
 return merge(left, right)
 
}

Conclusion

And that’s it! You now understand what each line in Merge Sort does, and how to write it. Congrats and good luck on your interviews!