Merge Sort in JavaScript

Explanations, gists, and examples

Image by Pxfuel

Just want the code? Scroll all the way down for three versions of the code:

1. Without comments (just plug and use).
2. Another with comments to understand the code.
3. Another with console logs and an example to see how everything works.

What is Merge Sort?

Merge sort is a sorting algorithm, where it’ll break down an issue into two or more similar subproblems until the initial problem gets easy enough to be solved directly.

Merge sort will divide an input array into two halves and keep doing that until it becomes a single element. Then, it’ll merge the two halves and sort them at the same time until we reach only a single array. Here’s an example of what a merge sort looks like.

Steps to Sort Arrays Using Merge Sort

The easiest implementation is using recursion functions. Here are the steps we’ll need to take to sort the array.

1. Check if the incoming array has a length of one — if it does, we return the element and have to start merging.
2. Otherwise, we keep on dividing the array in half until it matches the condition from Step 1.
3. When combining, we have two arrays: the left or the right array. We always assume both arrays are already sorted so we can just compare the beginning index of each array and add the smallest number.

GIF showing merge sort

Merge Sort in JavaScript (With Recursion)

Let’s start with the main function, the one where we take the unsorted array and split it until there’s only one element.

Taking an unsorted array, first check its length to see if it only has one element. If it does, we just return the array as it is.

Otherwise, we find the mid point (where to to split the array) and split the array into two, left and right.

This part is a bit tricky, we want to merge the two arrays, but first we got to organize the left and right and sort them in order before merging it. To do this, we use recursion and call the main function again, which will keep going until there’s only one element. In this case, it’s already sorted, so then we start merging the two arrays.

Now, we need to write the function to merge two arrays — assuming they’re already sorted in order.

Here we have two arrays: the left array and the right array. We assume everything is already sorted from lowest to highest. Before we start, we need three variables: a result array to push information into and two indexes keeping track of which index position is needed for each of the arrays.

let resultArray = [];
let leftIndex = 0, rightIndex = 0;

Then, we have a while loop that’ll keep going until one of the indexes goes out of the bounds of the array that it tracks.

while (leftIndex < leftArr.length && rightIndex < rightArr.length)

Next, we compare the two arrays and see which one is smaller. Once we find that, we’ll push that value into the result and increment the index tracker for the array.

if (leftArr[leftIndex] < rightArr[rightIndex]) { 
  resultArray.push(leftArr[leftIndex]);   leftIndex++;  
} else {   
  resultArray.push(rightArr[rightIndex]);   rightIndex++;  
}

This will keep on looping until one of the arrays run out of values (goes out of bound). After that, we want to add all the values from the unfinished array and push it into our result. We do this by using the spread operator inside of our push.

if (leftArr[leftIndex]) {   
  var unaddedElements = leftArr.slice(leftIndex)
  resultArray.push(...unaddedElements);  
} else {  
  var unaddedElements = rightArr.slice(rightIndex)
  resultArray.push(...unaddedElements);  
}

If you’re using JavaScript before the spread operator, you can do this by using concat instead.

if (leftArr[leftIndex]) {   
  var unaddedElements = leftArr.slice(leftIndex)
  resultArray = resultArray.concat(unaddedElements);
} else {  
  var unaddedElements = rightArr.slice(rightIndex)
  resultArray = resultArray.concat(unaddedElements);
}

Finally, you just have to return the result array, and you’re done.

return resultArray;

Just Here for the Code?

Here’s a link to the GitHub gist with all three files in one.

Version 1: Just the functions without any comments

Version 2: With comments

Version 3: With a console log and an example to test it out