Sorting Algorithm Race

Bubble sort makes exactly n(n−1)/2 comparisons in the worst case — about 2,000 for n=64. Every pass must scan the full remaining unsorted region with no early escape. Quicksort's partition places the pivot in its final slot and splits the problem into two sub-problems; each level of recursion does O(n) work over O(log n) levels, giving O(n log n) total. The catch: if the pivot always lands at one end — for example, sorted input with a last-element pivot — partitioning degrades to n sub-problems of size n−1, n−2, ... summing to O(n²). The mid-element pivot used here avoids that, which is why reversed input stays fast. Few-unique values are the interesting case: when many elements equal the pivot, swapping identical values wastes work and can push towards quadratic. Big-O tells you the growth class; constants, input sensitivity, and cache behavior determine which algorithm you actually ship.

This race scores each algorithm by counting comparisons and swaps, not with a stopwatch. Wall-clock time depends on your CPU, your browser, and whatever else is running, so the same code can look fast or slow on different machines. Counting operations gives a clean, reproducible measure of the actual work done: the same input always yields the same counts, letting you compare the algorithms themselves and not the hardware.

Tony Hoare invented quicksort in 1959 as a visiting student in Moscow, working on a machine-translation project. To look up a Russian sentence in a dictionary, he first had to put its words in alphabetical order — and the standard method was hopelessly slow. His fix, partitioning around a pivot, became one of the most-used algorithms ever written. The bars you watch race here trace an idea that started as a language problem, not a computing one.