Chapter Seven · Searching and Sorting
Searching and Sorting
What sorted data buys, and what it costs to get. Five topics: binary search, the quadratic sorts and where they still win, merge sort and quicksort, the limit no comparison sort can pass, and the hybrids, external sorts and merges that real systems run.
Sorted data is the cheapest index there is. It needs no pointers and no hash function, only order, and order turns "is this id here?" among two million ids from two million comparisons into 21. Every range query, every "nearest before", every prefix search and every merge of two lists leans on the same property. This chapter starts there, with binary search, and then asks what the order costs.
The answer comes in prices. The sorts people invent without being taught cost n squared, 500 billion comparisons for a million items, and still ship inside every library sort for the two cases where they win. Merge sort and quicksort reach n log n, 20 million comparisons for a million items, and differ in memory, stability and the one input that turns quicksort quadratic. Then comes a limit: no sort that only compares items can do better than about n log n, and the argument for it fits in a paragraph. Counting sort and radix sort step around it by never comparing at all.
The last topic is the sorting real systems run: Timsort in CPython, the hybrids in Java, C++, Go and Rust, the external merge sort that sorts a hundred gigabytes on one machine, and Lantern's two-term query, which intersects two sorted lists without sorting anything at query time. The cheapest sort, it turns out, is the one done once, in advance.