Merge sort algorithm in JavaScript

I can still remember the feeling, when we got the assignment at the university. We were suppose to solve four known sorting algorithms in a weeks time. Countless hours were spent, coffee was drunk as if it was water and the stress was lurking in the dark as the deadline was getting closer and closer by the hour. The algorithms we were suppose to solve was:

• bubblesort
• insertionsort
• merge sort
• quicksort

Bubble sort was simple, even back then when I was only about a year and a half into my coding journey. Insertion sort was also managable, but I can remember it was definitely tricker than the previous. But when merge sort was entering the stage, our whole class were chocked. Never have we gotten something complex as the two latter algorithms in our classes, and we all knew it was time to roll up the sleeves and get down to business if we were suppose to graduate one day.

There is something really special about algorithms. To me, there are no greater feeling than the feeling you have after fighting a hard battle with solving a complex algorithm, and seeing it work. That satisfaction of relief, proudness and power (yeah I'm a nerd) is so fulfilling.

Today, about 8 years after I sat there in my dorm room, I got the idea to revisit my good old sorting algorithm (which I have never ever even thought about since that time in university) and implement it once again. So in todays guide, we will solve the merge sort algorithm, in JavaScript.

Merge sort

I will not show any fancy pictures and gifs in this guide, I will give the explanation by my written words. If you want in depth information, I would recommend visiting this Wikipedia page that are explaining it very good.

Merge sort is an efficient sorting algorithm, which will recursively sort an array of numbers using a technique called divide and conquer. The idea is that, the algorithm processes the array by dividing the original list by half, and then each half by half - and it does that over and over again until each subarray is down to only 1 number. When the subarrays are down to one number, it is considered a sorted array (since it is only one number in the list).

Then, when we are down to arrays of one number, we are comparing the numbers to each other, and placing them back into the array one by one, in order.

Consider following array:

5,3,7,4,2,8

The arrays will be divided as following:

[5,3,7]  [4,2,8]

[5, 3], [7], [4, 2], [8]

[5], [3], [7], [4], [2], [8]

Then, each array will be compared and placed back

[5] vs [3]
[3, 5]

[7] vs [4]
[4, 7]

[2] vs [8]
[2, 8]

[3, 5] vs [4, 7]
3,4,5,7

[3, 4, 5, 7] vs [2, 8]
[2, 3, 4, 5, 7, 8]

Above example shows the process of the algorithm. I hope you understood it, otherwise, please read more about it so you fully understand before making your move onto the next section in this guide.

Implementation

Now, we will begin the fun part. The algorithm will have two functions - one for the dividing part and one for the comparing part.

Divide

Our dividing function, will work recursively and break down the array into smaller subarrays - basically, working down the indexes which we will use as our pointers in the original array.

const sort = (array, beg, end) => {
  if (beg >= end) {
    return;
  }
  const mid = beg + parseInt((end - beg) / 2);
  sort(array, beg, mid);
  sort(array, mid + 1, end);
  merge(array, beg, mid, end);
};

So what we are doing here, is basically finding the middle index, and then use that as our break point and then pass in the beginning index as the same and middle as the end for our left part of the array, and then middle (+1) as our beginning index and the end index as our end index for our right part. This will be done until our beginning index is larger or equal as our end index, then we will stop the recursion.

Our merge function, will accept the original array, and the three index values - which we will use to swap the values in the array.

Merge

To begin, we will create two temporary arrays, left and right. We will then fill them with the correct numbers according to the indexes. So the left will have values from beg -> mid and the right from mid + 1 -> end. The reason why we have +1 in the start index for the right, is to prevent that we will have duplicated numbers in the two arrays.

const merge = (arr, beg, mid, end) => {
  const left = [],
    right = [];

  for (let i = beg; i <= mid; i++) {
    left.push(arr[i]);
  }

  for (let i = mid + 1; i <= end; i++) {
    right.push(arr[i]);
  }

Next up, we need to add our values back into the original array, at its correct places.

We start by assigning some variables, our arrCounter will go from beg and upwards. Our leftCounter will keep track of our left array, and rightCounter our right array.

let arrCounter = beg,
  leftCounter = 0,
  rightCounter = 0;

Then, we will add back the numbers to the array. We will compare the left values with the right values and add to the array accordingly.

while (leftCounter < left.length && rightCounter < right.length) {
  if (left[leftCounter] <= right[rightCounter]) {
    arr[arrCounter] = left[leftCounter];
    leftCounter++;
  } else {
    arr[arrCounter] = right[rightCounter];
    rightCounter++;
  }
  arrCounter++;
}

Since our arrays can have different lengths, this is not yet enough. If our left side has e.g 4 numbers and the right 2 numbers, the rightCounter < right.length in the while loop might not be true anymore - so we need to make sure both our arrays will be checked. It will also happen if one side has much smaller numbers than the other, then the array with the higher numbers will not been "touched" in this loop.

So, we will add two additional loops for putting the numbers in the array, one for the left, and one for the right:

while (leftCounter < left.length) {
  arr[arrCounter] = left[leftCounter];
  leftCounter++;
  arrCounter++;
}

while (rightCounter < right.length) {
  arr[arrCounter] = right[rightCounter];
  rightCounter++;
  arrCounter++;
}

return arr;

There we go.

Full code

This is the full code:

const sort = (array, beg, end) => {
  if (beg >= end) {
    return;
  }
  const mid = beg + parseInt((end - beg) / 2);
  sort(array, beg, mid);
  sort(array, mid + 1, end);
  merge(array, beg, mid, end);
};

const merge = (arr, beg, mid, end) => {
  const left = [],
    right = [];

  for (let i = beg; i < mid + 1; i++) {
    left.push(arr[i]);
  }

  for (let i = mid + 1; i <= end; i++) {
    right.push(arr[i]);
  }

  let arrCounter = beg,
    leftCounter = 0,
    rightCounter = 0;

  while (leftCounter < left.length && rightCounter < right.length) {
    if (left[leftCounter] <= right[rightCounter]) {
      arr[arrCounter] = left[leftCounter];
      leftCounter++;
    } else {
      arr[arrCounter] = right[rightCounter];
      rightCounter++;
    }
    arrCounter++;
  }

  while (leftCounter < left.length) {
    arr[arrCounter] = left[leftCounter];
    leftCounter++;
    arrCounter++;
  }

  while (rightCounter < right.length) {
    arr[arrCounter] = right[rightCounter];
    rightCounter++;
    arrCounter++;
  }

  return arr;
};

Testing

In order to run some tests, we can simply run the following:

const arr = [17, 34, 21, 2, 43, 3, 5, 2];
sort(arr, 0, arr.length - 1);
console.log(arr); // 2,  2,  3,  5, 17, 21, 34, 43

And if we want to time it with some larger sets, we can do something as following:

const arr = [];
for (let i = 0; i < 100000; i++) {
  const random = Math.floor(Math.random() * 1000);
  arr.push(random);
}

console.time("mergesort");
sort(arr, 0, arr.length - 1);
console.timeEnd("mergesort"); // 23 ms

And now, you implement bubble sort and compare the result 😉

Summary

That's it for this guide. I hope you enjoyed it, and more importantly - that you learned from it. Any feedback or thoughts? Contact us and tell us what's on your mind.

Have a great day!