Merge sort

Divide, conquer, merge

Split in half, sort each half, then merge the two sorted halves. The whole algorithm is in that sentence; the only part with any content is the merge, and merging two sorted lists is easy precisely because they are sorted.

function mergeSort(a) {
  if (a.length < 2) return a;                    // one item is already sorted

  const mid = a.length >> 1;
  const left = mergeSort(a.slice(0, mid));       // trust the recursion
  const right = mergeSort(a.slice(mid));

  return merge(left, right);
}

The merge

Look only at the two fronts. Whichever is smaller must be the smallest item overall, because everything behind it is larger. Each comparison consumes exactly one item, so merging two halves totalling n items costs O(n).

That <= is the entire stability guarantee: on a tie, take from the left, which is the half that came first.

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++]);   // <= , not < — this is stability
    else out.push(right[j++]);
  }

  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);

  return out;
}

Where n log n comes from

Halving reaches one after log₂ n levels. Every level merges the entire input exactly once, which is n work. Multiply: n × log n, and no input can change it — merge sort has no bad case. At a million items that is 20 million operations rather than a trillion.

                [8 items]                    1 merge  of 8   = 8 work
        [4]                 [4]              2 merges of 4   = 8 work
    [2]     [2]         [2]     [2]          4 merges of 2   = 8 work
  [1][1]  [1][1]      [1][1]  [1][1]         ──────────────────────────
                                             log₂ 8 = 3 levels × n = 24

The price: memory

merge builds a new array, so the classic version uses O(n) extra memory — that is the trade for the guaranteed n log n and the stability. Quicksort sorts in place with O(log n) stack and gives up both.

An in-place merge sort exists, and it is slow and intricate enough that nobody uses it. The practical answer is to allocate one scratch buffer of size n up front and reuse it, which is what a real implementation does.

Why stability matters

That is the pattern that makes stability worth caring about — a table where the user clicks one column and then another, and expects the earlier ordering to survive inside the ties. It is why merge sort is used for objects even where quicksort would be faster, and why Java uses Timsort for objects and quicksort for primitives.

rows.sort((a, b) => a.name.localeCompare(b.name));   // by name
rows.sort((a, b) => a.score - b.score);              // then by score

/* with a STABLE sort: within each score, still alphabetical.
   with an unstable one: within each score, arbitrary. */