Sorting, Race by Race

Prelude

The asymptotic answer hides the real one

Every algorithms textbook lists the same table: mergesort, quicksort, heapsort — all $O(n \log n)$. Insertion sort, bubble sort, selection sort — all $O(n^2)$. End of story. Yet your standard library's sort is none of those three $n \log n$ algorithms. It's Timsort (Python, Java) or pdqsort (Rust, C++). Both spend a surprising amount of code calling insertion sort.

Asymptotics tell you how the cost scales. They don't tell you what the cost is. On 16 elements, insertion sort is faster than quicksort. On a nearly-sorted array of a million, Timsort beats vanilla quicksort by 10× by detecting existing runs. On adversarial input, a naïve quicksort degrades to $O(n^2)$ and a balanced mergesort doesn't.

The race below shows all of this directly. Five algorithms start on the same array and step one operation at a time. You can pick the input distribution, count comparisons and writes, and see the constants the big-O notation discards.

Step 1

The race

Each card shows an algorithm's current state: bars are values, the highlighted bar is the position currently being compared, swaps flash, sorted segments turn teal. All cards advance one operation per tick.

distribution size speed

unsorted bar comparing writing pivot / aux final position

Things worth trying:

Set distribution to already sorted. Insertion sort finishes in $n-1$ comparisons — its best case. First-element-pivot quicksort needs $\binom{n}{2}$ comparisons — its worst case. Same input, opposite outcomes.
Set distribution to reversed. Now bubble sort performs its maximum number of swaps. Mergesort doesn't care.
Set size to 24, distribution to random. Watch quicksort and mergesort finish in roughly the same wall-clock time despite different recursion structures.
Set size to 60, distribution to random. Insertion and bubble sort visibly lag behind the $n \log n$ contestants.

Step 2

Insertion sort — small-n champion

Walk through the array. For each new element, slide it leftward past every larger element until it lands.

Two facts that make insertion sort matter beyond textbook examples:

It is the best you can do on tiny arrays. Modern hybrid sorts (introsort, pdqsort, Timsort) call insertion sort below a threshold (typically 16 or 32). The asymptotic loss is bounded; the constants are unbeatable.
It is adaptive. On a $k$-nearly-sorted input ($k$ inversions), insertion sort runs in $O(n + k)$. On already-sorted, $O(n)$. Mergesort and heapsort don't speed up on adaptive input.
It is stable and in-place. Equal keys keep their relative order; no auxiliary memory.

Step 3

Mergesort — the deterministic n log n

Split the array in half, sort each half recursively, merge the two sorted halves in linear time. The merge is the heart of it:

Mergesort's guarantees:

$O(n \log n)$ worst case — no adversarial input slows it down.
Stable (with the standard implementation).
Pays $O(n)$ extra memory for the merge buffer. This is the reason mergesort lost the in-place fight to quicksort despite the better worst case.
External-sort friendly. Mergesort is the algorithm you use when the data doesn't fit in memory: split into RAM-sized runs, sort each, merge from disk. This is how databases sort terabytes.

Step 4

Quicksort — and the pivot question

Pick a pivot. Partition the array into "less than pivot", "equal", "greater than pivot". Recurse on the two outer partitions. The maths is similar to mergesort — a divide-and-conquer recursion that costs $O(n \log n)$ on average — but the implementation has one painful decision: which pivot?

Pivot strategies, ranked from "easy to break" to "production":

First element. The textbook introduction. On already-sorted or reverse-sorted input, partition is maximally unbalanced and quicksort collapses to $O(n^2)$.
Random pivot. Pick a uniformly random index per partition. Expected $O(n \log n)$ regardless of input distribution. An adversary who can see your random source can still hurt you, so use a real PRNG.
Median-of-three. Pivot = median of first, middle, last. Defeats sorted and reverse-sorted inputs (median-of-three on a sorted array picks the middle, which is the true median); doesn't defeat a crafted "killer" input. Cheap and very common.
Introsort. Start with quicksort; switch to heapsort if recursion depth exceeds $2 \log n$. Guarantees $O(n \log n)$ worst case while keeping quicksort's cache-friendly average. Used by std::sort in C++.
Three-way partition (Bentley-McIlroy). Handles arrays with many duplicates in $O(n)$ — the "few unique" distribution above collapses quicksort to linear time when you partition into "$<$, $=$, $>$" instead of "$\le$, $>$".

Why quicksort wins on real data despite a worse worst case. Cache locality. Each partition step touches contiguous memory; recursion descends into smaller and smaller contiguous ranges that fit in L1 / L2 cache. Heapsort and mergesort have access patterns that thrash the cache. Asymptotics don't see this — your CPU does.

Step 5

Heapsort — guaranteed n log n, in place

Build a max-heap from the array in $O(n)$ (Floyd's bottom-up heapify — see the Trees article). Then repeatedly extract-max into the last slot of the array, shrinking the heap by one. The extracted maxes accumulate in sorted order at the tail.

The combination is rare and useful: $O(n \log n)$ worst case, in place, no auxiliary memory. Why isn't it the standard? Cache. The implicit binary tree's array indices $i, 2i+1, 2i+2$ scatter accesses across memory; each sift-down is a series of cache misses. Quicksort touches contiguous regions; heapsort jumps. On real hardware quicksort wins by 2–3× for the same $n$.

Step 6

The big-O table — and what it leaves out

algorithm	best	average	worst	memory	stable	in place	adaptive
insertion	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	yes	yes	yes
bubble	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	yes	yes	yes
merge	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	yes	no	no
quick (random pivot)	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$ stack	no	yes	no
heap	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	no	yes	no
Timsort	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	yes	no	yes
introsort (pdqsort)	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(\log n)$ stack	no	yes	partial

The columns that the textbook table omits — stable, in place, adaptive — are exactly the ones that decide which sort your standard library actually ships.

Step 7

Beyond the comparison-sort ceiling

Any comparison-based sort must take at least $\Omega(n \log n)$ comparisons in the worst case — every permutation needs to be distinguishable, and a comparison tree of depth $d$ can only distinguish $2^d$ permutations.

If you don't need to compare — i.e., your keys are structured — you can do better.

Counting sort. Keys in $\{0, \ldots, k\}$? Count occurrences in $O(n + k)$, emit. Linear when $k = O(n)$. The block sort underlying radix.
Radix sort. Sort by least-significant digit, then next, then next. $O(d \cdot n)$ where $d$ is the number of digits. Faster than $n \log n$ on fixed-width integers; loses on cache behaviour for short arrays.
Bucket sort. Hash into $k$ buckets, sort each bucket, concatenate. Expected $O(n + k)$ on uniform input. Adversarial input drives it to $O(n^2)$.

One rule of thumb. For general-purpose ordering of comparable objects, use your language's built-in sort — it is Timsort or pdqsort and has been carefully tuned. Reach for a custom sort only when (a) you need a guarantee the standard sort doesn't give (worst-case $O(n \log n)$? stable across primitive and object?) or (b) your keys are structured enough for counting / radix / bucket to actually win.

Step 8

Reading list

Knuth, TAOCP Vol 3 — Sorting and Searching. Still the reference. The merge-network chapter alone is worth the cover price.
Sedgewick, 1978 — Implementing Quicksort Programs. The paper that introduced median-of-three and the in-place partitioning trick used for decades.
Bentley & McIlroy, 1993 — Engineering a Sort Function. The three-way partition that defeats the duplicates case; the partition-by-pseudo-median for large arrays. The paper that made qsort usable.
Peters, 2002 — Timsort original listsort.txt. The design notes of the Python sort. Beautiful engineering writing.
Auger, Nicaud, Pivoteau, 2018 — Merge Strategies: from Merge Sort to TimSort. The first thorough complexity analysis of Timsort, including the bug they found in the merge invariant.
Edelkamp, Weiss, Wild, 2020 — BlockQuicksort. Branchless partitioning that beats std::sort on modern CPUs by reducing branch mispredictions.