The Startup
Published in

The Startup

Merge Sort Algorithm 101

An overview of recursive and iterative merge sort implementations in JavaScript.

Photo by JOHN TOWNER on Unsplash

Here we go! So here are 3 implementations of the infamous Merge Sort Algorithm in vanilla JS. When I revisited this algorithm, I was reminded of my first glance at the logic behind it. From a high level, it’s not super difficult to wrap your head around. But as I descended further into the implementations I realized that a precise understanding of the algorithm is actually pretty hard!

Don’t feel bad if you struggle to understand the order of operations or even some of the patterns found in each implementation. We are going to break this down into manageable parts that are easier to wrap your head around.

High Level Overview

What is a Merge Sort Algorithm (MSA)? This algorithm is designed to take a list (or array) of unsorted numbers and rearrange them into a sorted ascending list of numbers. That’s it.

It has time-complexity of O(n log n) and a space-complexity of O(n), which means it’s reasonably fast but takes up a lot of space. So getting the best performance from this algorithm depends on the spatial resources of your application and size of the data set.

Here is a useful graph that compares the performance of various time-complexities including O(n log n):

Found on https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/

You might wonder why anyone would use this when JavaScript already contains the almighty .sort() method? Implementing this in an application with a lot of traffic gives you the chance to optimize the underlying code for specific use cases and will potentially offer better performance than a pre-packaged JavaScript method.

Challenge #1: Implement the merge sort algorithm yourself and do some performance testing to compare its runtime against the .sort() method using different size data sets.

So how does it work? The MSA is known as a divide and conquer algorithm because it breaks down the input into smaller manageable pieces to solve a larger problem.

Here is a written walk-through of a Top-Down Merge Sort:

  1. From a high level we can think of the MSA as a set of instructions that takes a list of unsorted numbers and reduces them (or breaks them down) into two separate lists until each list only has one number.
  2. At this point, it will compare the numbers and add them to a new list in ascending order (which is easy because there will only be two numbers to compare).
  3. It will repeat this process for all of the remaining unsorted numbers in the original list and recombine them until it produces a single sorted list.

Still confused? No worries. Here is a quick outline of what this might look like with arrays in JavaScript and a few resources to help you visualize the process.

                 let array = [2,1,4,3];// Break the input array into progressively smaller sub-arrays

leftArray = [2,1] | rightArray = [4,3]
leftArray = [2] rightArray = [1] | leftArray = [4] rightArray = [3]// Recombine the sub-arrays into sorted arrays until we have a single array with all sorted elements inside leftArray = [1,2] | rightArray = [3,4] [1,2,3,4]

A step-by-step visualization on hackerearth.comhttps://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/

Check out the illustration of a Top-Down MSA on interviewbit.comhttps://www.interviewbit.com/tutorial/merge-sort-algorithm/

Get the idea? No? Maybe? No problem, as we explore the implementations below things will start to clear up.

Implementations

The first implementation we are going to look at uses recursion and breaks the problem into two separate functions to keep this clear and concise.

The first function we are going to focus on is the actual MergeSort function that breaks down the initial unsorted array into smaller pieces. Then we will build out a merge function to stitch the arrays back together in sorted order.

Recursive MergeSort Function

Our goal here is to break the input array down into progressively smaller sub-arrays until we hit our base case (an array with only one number). The base case will return that number.

We will use recursion to perform this task on 2 arrays at the same time. When they both hit the base case, the values will be fed into our merge function (which we haven’t built yet) and get stitched back together into a final sorted array.

const array = [2,1,4,3];const recursiveMergeSort1 = (unsortedArray) => {  // Find the middle of the input array
const mid = Math.floor(unsortedArray.length / 2);
// Create 2 sub-arrays
const left = unsortedArray.slice(0, mid);
const right = unsortedArray.slice(mid);
// Create our base case, to return when the inputArray
// only contains 1 element

if (unsortedArray.length < 1) {
return unsortedArray;
}
// more code to be written...}

Stage 1 complete. We have the basis for our function to split an array in two and return if its length is less than 1. Now we can implement the recursive call to complete our MergeSort function.

const recursiveMergeSort1 = (unsortedArray) => {  // Find the middle of the input array
const mid = Math.floor(unsortedArray.length / 2);
// Create 2 sub-arrays
const left = unsortedArray.slice(0, mid);
const right = unsortedArray.slice(mid);
// Create our base case, to return when the inputArray
// only contains 1 element

if (unsortedArray.length < 1) {
return unsortedArray;
}
// This line will continually execute the recursive call until
// the base case is met for both params. Then the merge function
// will execute with those single elements
return merge(recursiveMergeSort(left), recursiveMergeSort(right));
};

Stage 2 complete. This is the final MergeSort function with recursion. Pretty simple after you wrap your head around the order of operations but it may take time to fully grasp how and when things get executed. If you are still having issues with this after we implement the merge function, try to console.log() various elements to understand when and how they execute.

Merge Function

Now to implement the merge function that pushes the sorted arrays back together.

const merge = (left, right) => {// Initialize a result array and 2 iterators
let result = [];
let i = 0;
let j = 0;

// Create a while loop that checks if both sub-arrays
// are larger than their iterators

while (left.length > i && right.length > j) {
// Push the smallest number to the result array
// and increase its iterator by 1

if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
};
};
// Return the result array plus the remaining value not pushed
// in the while loop above

return result.concat(left.slice(i)).concat(right.slice(j));
};

So there you have it, a merge function to complete our algorithm! If you are still a little befuddled by the code and how everything is suppose to work I would suggest you try this:

  1. Brush up on recursion, while loops, the .concat() and .slice() methods as they are used in our code above.
  2. Console.log() at every step of the way to really grasp the order of operations.

Here is a more complete look at the code:

const recursiveMergeSort1 = (unsortedArray) => {
const mid = Math.floor(unsortedArray.length / 2);
const left = unsortedArray.slice(0, mid);
const right = unsortedArray.slice(mid);
if (unsortedArray.length < 1) {
return unsortedArray;
}
return merge(
recursiveMergeSort1(left),
recursiveMergeSort1(right));
};
const merge = (left, right) => {
let result = [];
let i = 0;
let j = 0;

while (left.length > i && right.length > j) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
};
};
return result.concat(left.slice(i)).concat(right.slice(j));
};
const array = [2,1,4,3];
console.log(recursiveMergeSort1(array)); --> [1,2,3,4];

Alternate MergeSort Function

Photo by Alicia Steels on Unsplash

As with many algorithms there is usually more than one way to implement them in your code. So let’s take a look at an alternate version of a Recursive MSA in JavaScript. If you had trouble with the previous implementation, this might give you another way to conceptualize the process.

const recursiveMergeSort2 = (unsortedArray) => {  // Create left and right sub-arrays that split the
// unsorted array
let left = [];
let right = [];
let result;
// Base case, return the array when it only has 1 element
if (arr.length <= 1) {
return arr;
}
// Create variable that tracks middle index of unsorted array
let mid = Math.floor(arr.length / 2);
// Add all elements before middle index to left array
for (let i = 0; i < mid; i++) {
left.push(arr[i]);
}
// Add all elements affter middle index to right array
for (let j = mid; j < arr.length; j++) {
right.push(arr[j]);
}
// Create left and right values using recursion
let leftValue = recursiveMergeSort2(left);
let rightValue = recursiveMergeSort2(right);
// If left value less than right value merge them in that order
// else merge them in opposite order

if (leftValue <= rightValue) {
result = merge(leftValue, rightValue);
} else {
result = merge(rightValue, leftValue);
}

// Return the sorted result array
return result;
};

This implementation is fairly similar to the first mergeSort function we created. It utilizes a merge function once the left and right array have been split into single element arrays and achieves this outcome using recursion.

Here is a more complete look at the code:

const recursiveMergeSort2 = (unsortedArray) => {
let left = [];
let right = [];
let result;
if (arr.length <= 1) {
return arr;
}
let mid = Math.floor(arr.length / 2);

for (let i = 0; i < mid; i++) {
left.push(arr[i]);
}
for (let j = mid; j < arr.length; j++) {
right.push(arr[j]);
}
let leftValue = recursiveMergeSort2(left);
let rightValue = recursiveMergeSort2(right);

if (leftValue <= rightValue) {
result = merge(leftValue, rightValue);
} else {
result = merge(rightValue, leftValue);
}

return result;
};
const merge = (left, right) => {
let result = [];
let i = 0;
let j = 0;

while (left.length > i && right.length > j) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
};
};
return result.concat(left.slice(i)).concat(right.slice(j));
};
const array = [2,1,4,3];
console.log(recursiveMergeSort2(array)); --> [1,2,3,4];

Iterative Merge Sort

We aren’t done yet! That’s right we are going to run through a final implementation that takes an iterative (Bottom-Up) approach to the MSA. This implementation has a few more lines of code than the previous examples and involves 2 For Loops and 3 While Loops, along with a few more advanced variable initialization patterns.

The key to understanding this code is

const iterativeMergeSort = (arr) => {  // make a copy of the arr
let result = arr;
// length of the sort arr
let len = result.length;
// Creates a buffer to push all result elements into on each
// iteration
let buffer = [];

// size increases by 2 every loop
for (let size = 1; size < len; size *= 2) {
// leftStart increases by 2 * size every loop
// This acts as the first index of each pair in the arr

for (let leftStart = 0; leftStart < len; leftStart += 2 * size)
{
// The left index is a copy of the leftStart
let left = leftStart;

// The right index will be the smaller of the left +
// the current size or the length of the array

let right = Math.min(left + size, len);

// The left limit will be whatever the right index is
let leftLimit = right;
// The right limit will be the smaller of the right +
// the current size or the length of the array

let rightLimit = Math.min(right + size, len);
// The iterator will be a copy of the left
let i = left;
// The first while loop will check if the left and right
// indexes are both less than their limits
// Then it will push which ever value is smaller into
// the buffer array, increases the iterator and the
// index values, exit the loop
while (left < leftLimit && right < rightLimit) {
if (result[left] <= result[right]) {
buffer[i] = result[left];
left++
i++
} else {
buffer[i] = result[right];
right++
i++
}
}
// This loop checks if the left index is smaller than its
// limit if true it adds that value to the buffer

while (left < leftLimit) {
buffer[i] = result[left];
left++
i++
}
// This loop checks if the right index is smaller than its
// limit if true it adds that value to the buffer

while (right < rightLimit) {
buffer[i] = result[right];
right++
i++
}
}
// These are created after each inner loop completes // Create a temp array that is a copy of the original result
// array (unsorted values)
// The result array replaces all of its values with the buffer
// array (fully or partially sorted)
// The buffer then copies the unsorted temp array, which is
// used again in the next inner loop iteration
let temp = result;
result = buffer;
buffer = temp;
}
return result;
}
let array = [2,1,4,3];
console.log(iterativeMergeSort(array));

Ok, we are done! This implementation was a bit lengthier to get through but it offers you an nice alternative to the recursive solution. But I am sure you still have questions:

Which function is better for what use case? What is the time and space complexity of this implementation?, etc. All excellent questions… That I will let you tackle on your own!

Use both implementations, compare and contrast their performance in different conditions and tweak the code to fit your needs. Have fun with it and keep coding!

Challenge #2: Work through the above iterative merge sort code and figure out why it’s called the Bottom-Up approach?

Conclusion

I consumed a lot of articles, blog posts and tutorials on Youtube before I really understood how these implementations worked. In many cases I found examples in various tutorials that were either unclear or simply didn’t work. I spent a good amount of time experimenting with different code and even translated a few Python implementations that I though looked cool into JavaScript. The point is, that learning to code takes time, patience and a lot of critical thinking. Most importantly, it takes persistence and dedication to wrap your head around algorithms and there many implementations, so don’t give up. Try new things, optimize solutions you find on StackOverflow or LeetCode and… Keep learning!

Sources

Check out the working code for these implementations on my Github — https://github.com/twjsanderson/mergeSort

Take a look at one of the best articles I could find on Merge Sort (Recursion) by Karuna Sehgal for another perspectivehttps://medium.com/karuna-sehgal/a-simplified-explanation-of-merge-sort-77089fe03bb2

Here is the StackOverflow article that finally gave me a working iterative solutionhttps://stackoverflow.com/questions/32041092/implementing-merge-sort-iteratively

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store