Merge Sort Visualization

Merge sort is the classic proof that divide and conquer beats brute force. Instead of fixing one element at a time, it splits the array in half, recursively sorts each half, and then merges the two sorted halves, an operation that’s trivially linear because you only ever compare the two front elements. The animation below has a signature look: order emerges in waves, as small sorted runs pair up into larger and larger sorted blocks.

How it works

The recursion divides until it hits single elements (already sorted by definition), then all the real work happens in merge. Merging copies the two halves aside, then repeatedly takes the smaller of the two front values and writes it back into the array. Those are the rewrite flashes sweeping left-to-right across each region. Every level of the recursion tree touches all n elements once, and halving produces only log₂ n levels, so the total is O(n log n). For 100 bars that’s roughly 700 steps instead of the ~5,000 comparisons bubble sort needs. You can feel the difference at the same playback speed.

The trade-off is visible in the code: merge allocates left and right copies, so merge sort needs O(n) auxiliary memory. In exchange, you get something rare: the O(n log n) bound holds for any input. There is no unlucky case, no adversarial ordering: sorted, reversed, or random, the step count is essentially identical. Try shuffling: the animation’s rhythm never changes.

When interviewers ask about it

Merge sort is a top-three interview topic. It’s the canonical example for recurrence relations (you should be able to write T(n) = 2T(n/2) + O(n) and solve it), and its merge step is the famous “merge two sorted lists” problem, plus the core of “merge k sorted lists” and external sorting (sorting data too large for RAM). Interviewers also expect the comparison with quicksort: merge sort gives a guaranteed worst case and stability (equal elements keep their order, critical when sorting records by multiple keys) at the price of O(n) extra space, while quicksort is in-place but can degrade to O(n²). That’s also why Python and Java sort objects with a merge-based algorithm (Timsort).

The challenge covers merge sort twice: Day 6 introduces it alongside insertion sort, and Day 27: Mergesort Algorithm goes deep on the implementation and its analysis, with Day 29 putting it head to head against quicksort and heapsort.

Complexity at a glance

The exact code you are watching

This is the real generator that drives the animation above, read from sort-algorithms.js at build time, so the code and the visualization can never drift apart. Each yield is one visual step.

 1function* mergeSort(a) {
 2  yield* mergeSortRange(a, 0, a.length - 1);
 3  for (let i = 0; i < a.length; i += 1) {
 4    yield { type: 'markSorted', i: i };
 5  }
 6}
 7
 8function* mergeSortRange(a, lo, hi) {
 9  if (lo >= hi) {
10    return;
11  }
12  const mid = Math.floor((lo + hi) / 2);
13  yield* mergeSortRange(a, lo, mid);
14  yield* mergeSortRange(a, mid + 1, hi);
15  yield* merge(a, lo, mid, hi);
16}
17
18function* merge(a, lo, mid, hi) {
19  const left = a.slice(lo, mid + 1);
20  const right = a.slice(mid + 1, hi + 1);
21  let i = 0;
22  let j = 0;
23  let k = lo;
24  while (i < left.length && j < right.length) {
25    yield { type: 'compare', i: lo + i, j: mid + 1 + j };
26    if (left[i] <= right[j]) {
27      a[k] = left[i];
28      i += 1;
29    } else {
30      a[k] = right[j];
31      j += 1;
32    }
33    yield { type: 'overwrite', i: k, value: a[k] };
34    k += 1;
35  }
36  while (i < left.length) {
37    a[k] = left[i];
38    yield { type: 'overwrite', i: k, value: a[k] };
39    i += 1;
40    k += 1;
41  }
42  while (j < right.length) {
43    a[k] = right[j];
44    yield { type: 'overwrite', i: k, value: a[k] };
45    j += 1;
46    k += 1;
47  }
48}