JavaScript Algorithms: Merge Sort

Merge sort is a popular sorting algorithm that utilizes the “divide and conquer” approach. In this algorithm, an array is divided into two halves recursively until each half contains only one element. Then, the sorted subarrays are merged to form a single sorted array.

Let’s take an example to understand how merge sort works. Suppose we have an array:

[4, 3, 1, 2]

We first divide the array into two halves:

[4, 3]
[1, 2]

Then, we recursively divide these arrays:

[4]
[3]

and

[1]
[2]

Once we have reached arrays of one element, we start merging them in order:

[3, 4]
[1, 2]

Finally, we merge these two arrays to get the sorted array:

[1, 2, 3, 4]

Now, let’s consider another example with more items, this time using letters:

['e', 'g', 'a', 'd', 'f', 'c', 'b']

We divide the array into two halves:

['e', 'g', 'a']
['d', 'f', 'c', 'b']

Then, we divide the first array again:

['e']
['g', 'a']

and divide the second array:

['g']
['a']

Next, we divide the remaining part of the original array:

['d', 'f']
['c', 'b']

We divide these two arrays:

['d']
['f']

['c']
['b']

Now, we have a list of arrays, each containing one item:

['e']
['g']
['a']
['d']
['f']
['c']
['b']

We order these arrays in pairs:

['e', 'g']
['a', 'd']
['d', 'f']
['c', 'b']

Then, we order the first two arrays and the last two arrays:

['a', 'd', 'e', 'g']
['c', 'b', 'd', 'f']

Finally, we merge the two arrays we obtained:

['a', 'b', 'c', 'd', 'e', 'f', 'g']

To implement merge sort in JavaScript, we can use two functions. The first function, mergeSort, is the one we will call. The second function, _mergeArrays, takes care of merging the arrays. We prepend _ to its name to indicate that it should not be called directly.

Here are the implementation of both functions:

const _mergeArrays = (a, b) => {
  const c = [];

  while (a.length && b.length) {
    c.push(a[0] > b[0] ? b.shift() : a.shift());
  }

  // If we still have values, let's add them at the end of `c`
  while (a.length) {
    c.push(a.shift());
  }
  while (b.length) {
    c.push(b.shift());
  }

  return c;
};

const mergeSort = (a) => {
  if (a.length < 2) return a;
  const middle = Math.floor(a.length / 2);
  const a_l = a.slice(0, middle);
  const a_r = a.slice(middle, a.length);
  const sorted_l = mergeSort(a_l);
  const sorted_r = mergeSort(a_r);
  return _mergeArrays(sorted_l, sorted_r);
};

In the _mergeArrays function, we create an empty array c to store the merged values of arrays a and b that are passed as arguments. We then use a combination of shift() and push() to sort and merge these arrays.

The time complexity of merge sort is O(n log(n)), which makes it highly efficient for sorting large arrays.