Faster Sorting Algorithms

Introduction

In my sorting algorithms post I ended with "use the built-in sort, it's O(n log n), that's a whole post on its own." This is that post. The two algorithms that get you from O(n²) to O(n log n) are merge sort and quicksort, and once you see how they work, the sorting function in your language stops being a black box.

The trick both of them use is called divide and conquersplit a problem into smaller copies of itself, solve those, and combine the results. Instead of sorting the whole array, split it, sort the pieces, and put them back together.

Merge sort

Split the array in half. Sort each half (by splitting it in half, and so on, until each piece is one element, which is sorted by definition). Then merge the two sorted halves by repeatedly taking whichever front element is smaller.

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

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

  return merge(left, right);
}

function merge(left, right) {
  const out = [];
  let i = 0;
  let 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), right.slice(j));
}

Why O(n log n)? Halving an array of n items gives you log n levels of splitting. At each level, merging touches every element once, which is n work. n work times log n levels.

Merge sort is stable (equal values keep their order) and it's the same speed on every input, sorted or not. The cost is memory: the merge step needs a second array, so it's O(n) extra space.

Quicksort

Pick one element as the pivot. Move everything smaller than the pivot to its left and everything larger to its right. Now the pivot is in its final position. Recurse on the left part and the right part.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;

  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

Quicksort sorts in place, so no extra array. On average it's O(n log n) and in practice it's usually faster than merge sort because it works on the array where it sits, which is good for the CPU cache.

The catch is the pivot. If you always pick the last element and the array is already sorted, every partition puts everything on one side. The recursion depth becomes n instead of log n and you're back to O(n²). Real implementations pick the pivot randomly or use the median of three samples to avoid this.

Watch them work

Step through both. For merge sort, the shaded columns are the sub-array being worked on; watch the depth counter climb as it splits and fall as it merges. For quicksort, the purple bar is the pivot; everything it compares against lands on one side or the other. Hit Shuffle and compare the comparison counts on the same array.

What Array.prototype.sort actually does

JavaScript doesn't specify which algorithm sort uses, only that it has to be stable (since ES2019). What V8, the engine in Chrome and Node, actually runs is Timsort.

Timsort is a hybrid. It's merge sort at the top level, but:

• It scans for runs, stretches of the input that are already sorted (ascending or descending), and uses them as the pieces to merge instead of splitting all the way down to single elements. Real-world data is almost never truly random, so this is a big win.
• Runs that are too short get extended with insertion sort, which is fast on tiny arrays. This is why I said insertion sort was the sleeper hit in the last post.
• The merge step has tricks (galloping) to skip over chunks when one run is mostly smaller than the other.

The result is O(n log n) worst case, O(n) on already-sorted data, and stable. Python's sorted uses the same algorithm; Timsort was written for Python in 2002 and V8 adopted it in 2018.

Before that, V8 used quicksort for arrays over 10 elements and insertion sort below that, and it wasn't stable, which caused real bugs for people sorting tables by one column and expecting the previous sort to hold.

Which one should you know?

For interviews, know both well enough to write them and to explain the trade-offs:

• Merge sort: stable, predictable O(n log n), needs extra memory. Good for linked lists and external sorting (data too big for RAM).
• Quicksort: in place, fast in practice, bad pivots make it O(n²). The default in most C standard libraries.
• Timsort: what you're actually calling. Stable, adaptive, the best of both.

For real code, call .sort() with a comparator and move on.