Merge Sort

Merge sort is built on one small observation, and everything else follows from it:

Two already-sorted lists are easy to combine.

You never have to search. Look at the front of each list, take the smaller one, repeat. Both fronts are the smallest thing left in their list, so the smaller of the two is the smallest thing overall.

while (i < a.length && j < b.length) {  if (a[i] <= b[j]) out.push(a[i++]);  else out.push(b[j++]);}// then whatever is left over

Notice what the merge never does: it never looks past the front of either list, and it never goes back. One pass through both.

So sort by not sorting

If merging is easy, we can be lazy. Split the array in half, assume the two halves come back sorted, and merge them.

The halves get sorted the same way — split, assume, merge — until the pieces are one element long. A single element is already sorted, and that is where the recursion stops.

        [5, 2, 9, 1]
       /            \
    [5, 2]        [9, 1]        <- split
    /    \        /    \
  [5]    [2]    [9]    [1]      <- single elements, sorted by definition
    \    /        \    /
    [2, 5]        [1, 9]        <- merge
       \            /
        [1, 2, 5, 9]            <- merge

The code

function mergeSort(values: readonly number[]): number[] {
  if (values.length <= 1) return [...values];      // base case

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

  return merge(left, right);
}

function merge(a: readonly number[], b: readonly number[]): number[] {
  const out: number[] = [];
  let i = 0;
  let j = 0;

  while (i < a.length && j < b.length) {
    // <= not <. This is what makes the sort stable; see below.
    if (a[i]! <= b[j]!) out.push(a[i++]!);
    else out.push(b[j++]!);
  }

  return [...out, ...a.slice(i), ...b.slice(j)];   // whatever is left over
}

The last line matters. When one list runs out the other may still have items, and they are already sorted and already larger than everything placed — so they can be appended without comparison.

Reading the running time off the picture

You do not need any formula for this one. Look at the tree above.

How many levels? Each level halves the pieces, so it takes $\log_2 n$ levels to get down to single elements. For 1,000 items that is about 10; for a million, about 20.

How much work per level? Every level merges each element exactly once. The top merges $n$ items; the level below merges two halves of $n/2$, which is still $n$ in total. Every level costs $n$.

Stability, and the one character that provides it

A sort is stable if items that compare equal keep their original order.

That sounds academic until you sort twice. Sort employees by name, then by department: with a stable sort each department is still alphabetical by name. With an unstable one, that first sort is scrambled.

Look again at the comparison:

if (a[i]! < b[j]!) out.push(a[i++]!);
if (a[i]! <= b[j]!) out.push(a[i++]!);

a holds the elements that came earlier in the original array. On a tie, taking from a preserves their order; taking from b reverses it.

What it costs

The merge needs somewhere to put its output, so merge sort allocates. That is the real trade against quicksort: $O(n)$ extra memory in exchange for a guaranteed $O(n \log n)$ and stability.

Which is why the answer differs by situation:

• Arrays in memory — quicksort usually wins; no allocation, better cache behaviour.
• Linked lists — merge sort wins outright. Splitting is free and merging only relinks pointers, so the extra memory disappears.
• Data too large for memory — merge sort, always. Every database’s external sort for a large ORDER BY is this, because reading sorted runs sequentially is exactly what disks are good at.