Implementing Merge Sort in JavaScript

Joe Begley
Sep 7, 2018 · 2 min read

Merge Sort is used to merge two pre-sorted arrays into one sorted array.

It helps to think of this outside of the realm of code. Let’s say you have two groups of people, both arranged from shortest to tallest. If you wanted to combine them into one sorted group, how would you do it?

The answer is simpler than you might think. Let’s say the groups are ordered from shortest to tallest, and the new group also needs to be ordered from shortest to tallest.

The shortest person has to be the first person in one of the two lines. If two people are the shortest person in their respective groups, the shorter of the two is the shortest person overall (or it’s a tie).

So, we pull that person out and tell him or her to make a new group. We then repeat the process, telling the shortest remaining person to get to the end of the new group, where they reign supreme as the tallest person, if only for a moment.

Once we’ve repeated the process enough that one of the groups is empty, there must be one group remaining with people in it. The group with people in it stays in order and gets to the back of the new group.

Just like that, you have your single sorted group.

Now, let’s do this with code.

You have two sorted arrays.

let arrA = [0,1,3,4,4,5,7,10,13,14,16,17,18,19,21,24,25,27,28,30];let arrB = [1,2,3,5,7,8,10,11,12,13,15,18,22,22,23,25,28,28,29,29];

Then there is the new, single sorted array.

let singleSorted = [];

The first element of those arrays must be the smallest element. Whichever one is smallest gets removed from its array and joins the new array.

if (arrA[0] < arrB[0]) {
singleSorted.push(arrA[0]);
arrA.shift();
} else {
singleSorted.push(arrB[0]);
arrB.shift();
}

This process gets repeated until one of the arrays is empty. We can replicate this process with a while loop.

while (arrA.length && arrB.length) {}

Then we put the process that we want to repeat in the loop.

while (arrA.length && arrB.length) {
if (arrA[0] < arrB[0]) {
singleSorted.push(arrA[0]);
arrA.shift();
} else {
singleSorted.push(arrB[0]);
arrB.shift();
}
}

This loop will finish executing once one of the groups is empty. To finish the process here we could figure out which array is empty and move everything in that array to the end of the single sorted array.

A simpler solution is to just concatenate ArrA and ArrB to the back of singleSorted. JS will just not append anything with the empty array and the solution will be fine.

singleSorted.concat(arrA,arrB);

Now, we just wrap this in a function and we get a full solution.

function mergeSort(arrA,arrB) {
let singleSorted = [];
while (arrA.length && arrB.length) {
if (arrA[0] < arrB[0]) {
singleSorted.push(arrA[0]);
arrA.shift();
} else {
singleSorted.push(arrB[0]);
arrB.shift();
}
}
return singleSorted.concat(arrA,arrB);
}

And if we run the function with our two arrays, we get this.

let arrA = [0,1,3,4,4,5,7,10,13,14,16,17,18,19,21,24,25,27,28,30];
let arrB = [1,2,3,5,7,8,10,11,12,13,15,18,22,22,23,25,28,28,29,29];
let mergedArr = mergeSort(arrA,arrB);
/* MergedArr [0,1,1,2,3,3,4,4,5,5,7,7,8,10,10,11,12,13,13,14,15,16,17,18,18,19,21,22,22,23,24,25,25,27,28,28,28,29,29,30] */

Just in case you didn’t get it, here’s a YouTube video explaining the process.

Joe Begley

Written by

Web Developer. Standup Comic. Bass player. Connoisseur of all things fun.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade