The History of Sorting

Abstract

Sorting is the oldest problem in data processing: it predates the computer by half a century, consumed by one 1960s estimate a quarter of all machine time ever sold, and produced the first program ever written for a stored-program computer. It is also the field’s best miniature of how algorithms mature: from mechanical card sorters through von Neumann’s mergesort and Hoare’s quicksort to a proved lower bound that says how good comparison sorting can ever get, and finally to industrial hybrids like Timsort. The modern punchline is humbling: in 2015 a formal verification tool found a crash bug in Timsort that had been shipping inside Java and Python for over a decade, and the first fix Java applied turned out to be wrong too.

Sorting Before Computers

The sorting industry is older than the computer industry. Herman Hollerith’s tabulating machines processed the 1890 US census, and by 1901 he had added an automatic sorter that routed punched cards into pockets by the value of one column. Running the cards through once per digit, least significant digit first, sorts the whole deck: what programmers now call radix sort was standard office practice decades before anyone coded it. Machine rooms full of card sorters (IBM’s Type 80 sorter, introduced in 1925, processed 450 cards a minute) were the data centers of the punched-card era, and “sorting” meant a physical department with staff.

This history explains an oddity of the first computers: they had something to prove against furniture. Electronic machines were obviously faster at arithmetic, but whether an expensive computer could beat a cheap, reliable card sorter at ordinary business data processing was a live commercial question into the 1950s.

Von Neumann’s First Program

That question is why the first program ever written for a stored-program computer was a sort. In 1945, while the EDVAC existed only on paper, John von Neumann wrote out a complete sorting routine for it: a mergesort, repeatedly merging already-ordered sequences into longer ones, an approach with guaranteed n·log n running time that also suited data streamed from tapes. Donald Knuth, who analyzed the manuscript in a 1970 paper, noted the point of the exercise: von Neumann wanted evidence that the proposed machine, with its single memory for code and data, could handle the bread-and-butter work of the punched-card equipment it aimed to replace. Sorting was the benchmark reality check for the Von Neumann Architecture itself.

The commercial machines that followed made sorting their showcase. Betty Holberton, one of the six original ENIAC programmers, wrote a sort-merge generator for UNIVAC in 1951: given a description of the records, it generated a tailored tape-sorting program, which makes it a strong candidate for the first program that wrote programs. Grace Hopper cited it as a direct influence on her first compiler. For the tape-drive generation, “external sorting” (data far larger than memory, streamed and merged between reels) was the discipline’s core problem, and Knuth’s The Art of Computer Programming Volume 3 (1973) still devotes half its bulk to it. Knuth also preserved the era’s most quoted statistic: computer manufacturers estimated in the 1960s that over a quarter of all machine running time was spent sorting.

Quicksort

The in-memory breakthrough came from a waiting room. In 1959 the 25-year-old Tony Hoare, on an exchange year in Moscow, worked out quicksort while waiting for unreliable Soviet computer time: pick a pivot element, partition the array around it, recurse on both halves. Published as Algorithm 64 in the Communications of the ACM in 1961, it averages n·log n comparisons with constant factors and memory behavior good enough that, sixty years on, its descendants still sit inside the C library’s qsort and most languages’ default sorts. The same few years produced the other classics: Donald Shell’s diminishing-increment Shellsort (1959), Harold Seward’s counting sort (1954, in an MIT master’s thesis), and J. W. J. Williams’s heapsort (1964), which contributed a permanent data structure, the heap, as a side effect. Sorting became the field’s shared teaching corpus, the set of examples on which generations learned what “analysis of algorithms” means.

The Wall

Sorting is also where computer science first hit a proved wall. Any algorithm that sorts by comparing pairs of elements can be drawn as a decision tree; a tree with enough leaves to distinguish all n! orderings must have depth at least log₂(n!), which is about n·log₂ n. So no comparison sort, however clever, can beat n·log n in the worst case: mergesort and heapsort were already, in this exact sense, as good as it gets. The argument, folklore among specialists by the 1950s and laid out in Knuth’s Volume 3, taught the field a lesson bigger than sorting: some limits are not engineering failures but mathematics, and you escape them only by changing the rules of the game. Radix sort escapes by not comparing (it inspects digits, as Hollerith’s machines did), which is why it can run in linear time and why the “fastest sort” question has no one answer.

Engineered Sorts

Once the theory settled, the frontier moved to engineering: real inputs are not random, and real machines are not comparison counters. David Musser’s introsort (1997) starts as quicksort and switches to heapsort if the recursion goes bad, capping the worst case; it became the standard C++ std::sort. Timsort, written by Tim Peters for Python in 2002, went further: it hunts for runs, stretches of data that are already ordered, and merges them, so nearly-sorted input (most input, in practice) sorts in nearly linear time. Timsort spread from Python to the Java standard library (2011) to Android to V8, the JavaScript engine, making it plausibly the most-executed algorithm invented in the 21st century. Rust’s standard library adopted a pattern-defeating quicksort in the same spirit: the modern default sort is a portfolio of 1960s algorithms with an adaptive dispatcher on top.

The Bug That Shipped for Thirteen Years

The coda belongs to formal methods. In February 2015 a group of researchers (Stijn de Gouw, Jurriaan Rot, Frank de Boer, Richard Bubel, and Reiner Hähnle) set out to formally verify Java’s Timsort implementation with KeY, a theorem prover for Java, expecting a routine demonstration on famous industrial code. The proof would not close. The reason was real: Timsort maintains an invariant on its stack of pending runs, the implementation re-established it incompletely, and for adversarially constructed inputs of tens of millions of elements the run stack overflows its preallocated array and the sort crashes. The bug had been present since 2002 and had shipped in Python, in Java since version 7, and in every Android device.

The responses diverged instructively. Python applied the researchers’ fix, repairing the invariant. OpenJDK’s maintainers instead enlarged the stack, judging the full fix too invasive; a 2018 worst-case analysis by Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau proved the enlarged stack was still too small, and Java had to fix it again. A sorting routine read by thousands of expert eyes over thirteen years carried a crash bug that fell out of the first serious attempt at a machine-checked proof. Hoare, who spent his career after quicksort arguing that programs should be proved rather than debugged, could hardly have commissioned a better advertisement.

Dead End: Bubble Sort

The most famous sorting algorithm is one nobody should use. Bubble sort (repeatedly swap adjacent out-of-order elements) is quadratic like the other naive sorts but slower in practice than its siblings insertion sort and selection sort, and it lost every technical comparison decades ago. Knuth’s verdict in Volume 3 stands: it “seems to have nothing to recommend it, except a catchy name”. Yet it survived for generations as the default first sorting algorithm in textbooks, a pedagogical zombie propagated, as Owen Astrachan’s 2003 archaeology of the algorithm showed, mostly by earlier textbooks. Its cultural moment came in November 2007, when Eric Schmidt, interviewing candidate Barack Obama on stage at Google, asked him the most efficient way to sort a million 32-bit integers. Obama, briefed or lucky, answered: “I think the bubble sort would be the wrong way to go.” It is the only algorithm ever disavowed by a future US president, which is, fittingly, a distinction with no technical merit whatsoever.