Merge sort
Tags: algorithms, sorting, javascript, computerscience
Published: 2020-01-21 12:27:19

In my mind, merge sort is a more complex version of [quick sort](https://dev.to/jamesrweb/quick-sort-4e6b) 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:

```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](https://dev.to/jamesrweb/quick-sort-4e6b#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:

```javascript
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:

```javascript
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](https://en.wikipedia.org/wiki/Big_O_notation) 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](https://en.wikipedia.org/wiki/Comparison_sort) algorithm.

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

| Input size | Time complexity (Big O)       |
|------------|-------------------------------|
| 10         | O(10 log 10) = O(10)          |
| 100        | O(100 log 100) = O(200)       |
| 1000       | O(1,000 log 1,000) = O(3,000) |

Compared to [quick sort](https://dev.to/jamesrweb/quick-sort-4e6b), 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!