Implement Merge Sort in JavaScript

Implement Merge Sort in JavaScript

This article is part of a series covering sort algorithms in JavaScript. You can find the rest of the series here. Today I’ll be covering the ins and outs of merge sort. This is probably the first useful sorting algorithm I’m covering. Merge sort is a stable sort just like insertion sort. Not sure what a stable sort is? I explain it in my introduction to sort algorithms.

Analysis

So where does the name come from? It’s based on the idea that it’s easier to merge two already sorted lists than it is to sort one unsorted list. Therefore, merge sorts start by creating n number of single item lists (n is the total number of items in the list). Merge sort then starts to combine these single item lists into a single sorted list.

Complexity

The time complexity of this algorithm, at worst case, is linearithmic — O(log n!). This is one of the more efficient sorting algorithms, which is why most browsers use merge sort as the built in Array.sort method.

One thing to note about merge sort is that it’s not ‘in place’. During merging, it creates a copy of the entire array being sorted, which means it copes more than a constant number of elements at some time. Due to this, the space complexity of this algorithm is actually greater than most, and are not commonly used in larger systems where space is at a premium. Some in place sorts include selection sort and insertion sort.

Simplified Pseudocode

Recursively divide list into n lists
Call merge on each sublist then until combined into one list

Detailed Pseudocode

function mergeSort(array) {
  If array length < 2
    Return array

  Create var for middle index of array
  Create var for far left index of array
  Create var for far right index of array
  Recursively call mergeSort function
}
Function merge (node1, node2) {
  Create var for result array
  While node1 length > 0 and node2 length > 0
    If node1[0] < node2[0]
      Shift node1 and push to result array
    else 
      Shift node2 and push to result array
  Return concat node1 or node2 (depending if node1 is empty or not)

Code

function mergeSort (arr) {
    if (arr.length < 2) {
      return arr;
    }

    var mid = Math.floor(arr.length / 2);
    var subLeft = mergeSort(arr.slice(0, mid));
    var subRight = mergeSort(arr.slice(mid));

    return merge(subLeft, subRight);
}

function merge (node1, node2) {
    var result = [];
    while (node1.length > 0 && node2.length > 0)
        result.push(node1[0] < node2[0]? node1.shift() : node2.shift());
    return result.concat(node1.length? node1 : node2);
}