Merge sort

In my mind, merge sort is a more complex version of quick sort but this complexity brings more consistent performance gains over quick sort, which is impressive considering that quick sort is already O(n log n) in performance which is as fast as we can get for a comparison algorithm.

Implementation

Below we can see an example of merge sort written in JavaScript:

function merge(left, right) {
  const result = [];

  while(left.length || right.length) {
    if(left.length && right.length) {
      result.push(left[0] < right[0] ? left.shift() : right.shift());
    } else {
      result.push(left.length ? left.shift() : right.shift());
    }
  }

  return result;
}

function mergeSort(array) {
  if(array.length <= 1) return array;

  const middle = array.length / 2 ;
  const left = array.slice(0, middle);
  const right = array.slice(middle, array.length);

  return merge(
    mergeSort(left),
    mergeSort(right)
  );
}

We have 2 function declarations, one to run the merge sort algorithm over an array and another to merge the left and right arrays which we will generate in that algorithm.

Looking at the mergeSort function we can see that just like in our quick sort implementation we return the array straight away if it contains 1 or less items. If we have more than one item, we reach for the middle of the array and take left and right slices from the array using the middle as the cut off point for each side. You may be asking yourself:

What happens if the array has a length which is odd?

Well, let's look at a working example with an even length array:

const array = [3, 1, 4, 2];
const middle = array.length / 2; // 2
const left = array.slice(0, middle); // [3, 1]
const right = array.slice(middle, array.length); // [4, 2]

And an odd length array:

const array = [3, 1, 4];
const middle = array.length / 2; // 1.5
const left = array.slice(0, middle); // [3]
const right = array.slice(middle, array.length); // [1, 4]

As we can see, in JavaScripts case, if we slice with a float, the float is floored and with the example above we can see how the left and right slices are formed! Ok, so, from here, we will move onto the return value of the mergeSort function which basically recursively splits the left and right arrays and merges them back together in the right order via the merge function which we will look at next.

The merge function runs a loop that lasts for as long as the left and right arrays have items within them. With each iteration, we check if left AND right have items and if so, we compare the first items from each side and if the first item of left is less than the first item of right, we push the first item of left into the result array otherwise the first of right. If left OR right have no length, we check which one has items still and add the first item from it into the result array until no items remain and the loop exits, whereby we finally return the sorted output array.

Use case and Performance

Merge sort has a great Big O time complexity of O(n log n) on average. This means that the time it takes to run the algorithm is the square of the size of the input array, otherwise known as linearithmic time which is the fastest possible time complexity for a comparison sort algorithm.

Let's look at some example runtimes from given input sizes:

Compared to quick sort, these performance statistics aren't much to write home about but that only accounts for the average case, merge sort trumps quick sort in performance because the worst case is also O(n log n) whereas the worst for quick sort is O(n²). Merge sort is great and adds complexity as a tradeoff for performance. In general though, it is up to you if you prefer quick sort or merge sort but both are great divide-and-conquer option to have under your belt!