Thought Toys · Computation & information · Exhibit 23
The same shuffled bars, sorted five different ways. Some methods plod — comparing every pair, again and again. Others split the work cleverly and finish in a blink. Watch the comparison counter, then drag the pile bigger: the slow ones don't just lose, they lose by more and more. That widening gap is what "big-O" really means.
—
—
—
Every bar is a number; the job is to line them up shortest-to-tallest. Each method gets the same shuffled row, and we count what it actually does — every comparison (is this bar taller than that one?) and every move. The two bars under comparison glow amber; a bar that just moved flashes and fades.
The three plodders all share a flaw: they compare neighbours over and over. Bubble sweeps the row swapping out-of-order pairs, again and again. Selection scans the whole rest of the row each time to find the next smallest. Insertion slides each new bar back into the sorted part. On a pile of n bars they each do roughly n²⁄2 comparisons — the work grows with the square of the size.
The two quick ones don't compare everything to everything. Merge sort splits the row in half, sorts each half, then merges the two sorted halves in one pass. Quicksort picks a pivot and throws smaller bars left, bigger right, then repeats on each side. Both finish in about n·log₂n steps — and that is a different kind of number. At a few bars the two kinds look the same; the real story is what happens when you drag the size up. Doubling the pile roughly doubles a fast sort's work, but quadruples a slow one's — so the gap doesn't just persist, it widens, forever. At 70 bars an O(n²) sort already does six times the work of an O(n log n) one; at 70 thousand it would do thousands of times more. That is the whole reason "which algorithm" matters more than "which computer." (The sort your computer actually runs is usually Timsort — a hybrid that does plain insertion sort on tiny chunks, where its low overhead wins, then merges them: it exploits exactly the crossover you're looking at.)
improve/verify/23-sorting.js): all five sorts return a sorted permutation; the
exact laws hold (bubble & selection & insertion hit n(n−1)⁄2 in
their worst case, bubble & insertion hit n−1 already-sorted; merge stays ≤
n⌈log₂n⌉, quick comfortably under n²⁄4 on random data — its
average, not a guarantee) and the
O(n²):O(n log n) ratio strictly increases with n.
Counter-example: a bubble sort with its inner bound off by one stops one
pair short and leaves a reversed row unsorted — the proof's check catches it,
so "sorted" means sorted, not assumed.
Also in Computation & information: PageRank & the random surfer →
← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 23.