Experiment № 076 · The story
Where You Cut
Why I picked it
Seventy-five experiments in and I had never done a sort — the most-executed family of algorithms on earth, and I'd skipped it because animated bars feel like a first-week exercise. What changed my mind was remembering what quicksort actually is. Tony Hoare invented it in 1960 as a graduate student in Moscow, trying to sort words for a Russian–English translation machine, and the idea is one sentence: pick any element, put everything smaller to its left and everything bigger to its right, then do the same to each side. There is no clever merging afterwards. There is no afterwards at all — once the two sides exist, they never speak to each other again. And that one sentence contains both the fastest general-purpose sort in practice and a way to spend n²/2 comparisons on an array that was already sorted. Same code. The only difference is where you cut.
What I enjoy about it
The dashed pink line. Partitioning is usually explained with index arithmetic, but on screen it's just a horizontal line at the pivot's height: everything under the line is going left, everything over it is going right, and the sweep is only carrying out that sentence. Then there's the call tree at the bottom, which is where the drama is. With a random pivot it grows fat and shallow — twenty levels of nothing much. Ask for first and hand it an already sorted array and the tree topples over into a staircase: one bar peeled off per level, the nesting as deep as the array is long, the comparison counter grinding through half of n² to accomplish precisely nothing. My other favourite is switching the scheme to three-way with few values: the equal block settles wholesale, and a run that took thousands of comparisons finishes in a few hundred. And in you choose mode I dare you to beat the machine — you'll find that aiming near the middle of the heights, not the middle of the row, is the entire skill.
Something you might take away
Two things. First, work is conserved between splitting and joining: merge sort splits carelessly down the middle and pays for it in the merge; quicksort pays everything up front in the partition and gets to skip the merge entirely. When you're designing anything recursive, ask which end you'd rather pay at — but don't expect a free lunch at both. Second, and this is the one I actually use: randomising the pivot doesn't make quicksort faster on average by even a single comparison. What it does is move the worst case out of the input and into the dice. Sorted and nearly-sorted data is not some rare adversarial edge case — it is the most common shape real data arrives in, so a deterministic pivot fails exactly when you'd least like it to. Trading a worst case that the world can hand you for one that requires bad luck is often the whole point of adding randomness to a program.