Merge sort in detail

Merge sort: divide and conquer

Merge sort is the quintessential example of the divide and conquer strategy. It has a complexity of O(n log n), much better than the O(n²) of bubble sort for large inputs, and it is stable (it keeps the relative order of equal elements).

The idea boils down to three steps:

1. Divide: split the array in half until you reach chunks of size 0 or 1, which are already sorted by definition (the base case).
2. Conquer: sort each half recursively.
3. Combine: merge the two already-sorted halves into a single sorted array.

The merge function

The heart of the algorithm is merging two already-sorted arrays into one. We use two indices (one per array) and always pick the smaller of the two pending elements:

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  // One of the two is already exhausted; we append whatever remains of the other.
  return result.concat(left.slice(i)).concat(right.slice(j));
}

The mergeSort function

With merge solved, mergeSort just divides and delegates:

function mergeSort(arr) {
  if (arr.length <= 1) return [...arr]; // base case

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

Notice that slice creates copies: the algorithm does not mutate the original array. Why O(n log n)? There are log n levels of division, and at each level a total of n elements are processed during merging.

Examples

Merge sort with a trace of the divisions

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return out.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(arr) {
  if (arr.length <= 1) return [...arr];
  const mid = Math.floor(arr.length / 2);
  console.log("Dividing:", arr.slice(0, mid), "|", arr.slice(mid));
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
console.log("Sorted:", mergeSort([5, 2, 8, 1, 9, 3]));