Implementing merge sort using JavaScript (with code example)

The merge sort is one of the more advanced sorting algorithms that’s quite efficient in sorting large amounts of data.

The algorithm uses the recursive function concept with divide and conquer strategy to efficiently sort a given list of elements.

To understand the concept of merge sort easily, let’s start with a small example array as follows:

               [5, 2, 4, 3, 1]

First, split the array into two halves until there is only one element in each array:

              [5, 2, 4, 3, 1]
            [5, 2, 4]  |   [3, 1]
        [5, 2]    [4]  |   [3]   [1]
      [5]   [2]   [4]  |   [3]   [1]

Once done, start the second phase by merging and sorting two closest arrays.

The smaller element will be pushed first to the new empty array, effectively sorting the array one step at a time.

Here’s an illustration of the merging:

      [5]   [2]   [4]  |   [3]   [1]
         [2, 5]   [4]  |   [1, 3]
         [2, 4, 5]     |   [1, 3]
               [1, 2, 3, 4, 5]

Now that you know how the merge sort works, let’s see how you implement one using JavaScript.

Implementation of merge sort using JavaScript

To implement merge sort using JavaScript, you need to first create a function that merges two arrays.

Obviously, this function will accept two arrays, and it needs to sort the two arrays correctly starting from the smallest element.

Let’s first create the function and sort the arrays as follows:

function merge(left, right) {
  let sortedArr = []; // the sorted elements will go here

  while (left.length && right.length) {
    // insert the smallest element to the sortedArr
    if (left[0] < right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
}

When the while loop above is finished, you would have the elements of two arrays sorted inside the sortedArr variable.

But since the two arrays length can be uneven, you may have one last element available in either left or right array:

Take a look at the following merge() simulation:

merge([3, 4, 7], [2, 5]);

function merge(left, right) {
  let sortedArr = []; // the sorted elements will go here

  while (left.length && right.length) {
    // insert the smallest element to the sortedArr
    if (left[0] < right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }

  console.log(sortedArr); // [2, 3, 4, 5]
  console.log(left); // [7]
  console.log(right); // []
}

As you can see above, the left element still has the number 7 because there’s no element to compare with.

To solve this problem, you can simply use the spread operator and put the leftover element into the mix:

function merge(left, right) {
  let sortedArr = []; // the sorted elements will go here

  while (left.length && right.length) {
    // insert the smallest element to the sortedArr
    if (left[0] < right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }

  // use spread operator to combine the three arrays as one
  return [...sortedArr, ...left, ...right];
}

With that, you have the merge() function for the merge sort ready. Now you only need a function that splits an array into 1 size.

Here’s an example of the mergeSort() function:

function mergeSort(arr) {
  const half = arr.length / 2;

  // the base case is array length <=1
  if (arr.length <= 1) {
    return arr;
  }

  const left = arr.splice(0, half); // the first half of the array
  const right = arr;
  return merge(mergeSort(left), mergeSort(right));
}

The mergeSort() function will first split the given array parameter in half until the array length is one or smaller. The arrays will then be passed to the merge() function, which will start merging the arrays until all elements are merged.

And that’s how you implement a merge sort with JavaScript. Let’s look at the performance score of merge sort next.

The efficiency of merge sort

The merge sort algorithm has the time complexity of O(logN), meaning that the time required to execute N number of elements will rise in logarithmic proportion.

If sorting an array of 10 elements requires 1ms, sorting an array of 100 elements will take 2ms.

Merge sort is much more efficient in time complexity than the insertion sort, but merge sort also consumes more space because the sorting is not in-place and the recursive call will be threaded.

The merge sort will take O(N) space to perform the sorting.