Sorting in the Real World

No mainstream language ships a textbook sort. CPython sorts with Timsort, Java ships two different sorts, and C++, Go and Rust ship tuned hybrids. Each is a merge sort or a quicksort that hands small pieces to a simple sort and guards against its own worst case.

Past the library, two sorting problems reach every system sooner or later: data bigger than memory, and lists that are already sorted and need combining. The second is what Lantern does for every query with two terms, and it turns out to need no sorting at all.

Timsort: Sorting the Data People Have

Real data is rarely random. It arrives as ascending or descending runs: records appended in time order, a log, a sorted list with a few new items at the end. Timsort, written by Tim Peters for CPython in 2002, is built around that fact. It scans the input for natural runs and reverses descending ones in place. It extends any run shorter than a minimum length, between 32 and 64 items, with binary insertion sort, the small-range sort of The Simple Sorts. Then it merges runs of similar size, and when one run keeps winning a long stretch of comparisons it gallops: it jumps ahead 1, 2, 4, 8 items and halves back, instead of comparing one item at a time.

The payoff is that order in the input becomes speed. Measured on Python 3.15, sorting a million sorted items took 999,999 comparisons, and so did a million reversed items: one pass to find a single run. A million random items took 18.6 million. A sorted million with 100 random items appended took 1,003,243. Since CPython 3.11, the order in which runs are merged follows the Powersort rule of Ian Munro and Sebastian Wild, which is provably close to the cheapest possible order of merges.

The Hybrids Other Languages Ship

Java sorts objects with Timsort, adopted from Python in Java 7, because two equal objects can be told apart and the order of ties shows. It sorts primitive arrays, such as an array of ints, with a dual-pivot quicksort by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch, because two equal ints are indistinguishable and stability is invisible. Choosing different sorts for the two cases is not an inconsistency; it follows from what the caller can observe.

GCC's C++ library implements std::sort as introsort: a quicksort that watches its own recursion depth and switches to heapsort, from Chapter 6, when the depth passes twice the base-2 logarithm of n, which guarantees n log n on any input, and that finishes by running insertion sort over ranges of up to 16 items. Go, since version 1.19, uses pattern-defeating quicksort. Rust, since version 1.81, uses driftsort for its stable sort and ipnsort for its unstable one. Every one of them hands small ranges to a simple sort, because at a dozen items the simple sort wins.

Sorting Data Bigger Than Memory

To sort 100 GB with 8 GB of memory, read a memory-sized chunk, sort it in memory, and write it back to disk as a sorted run. Thirteen chunks make 13 sorted runs. Then merge all 13 in a single pass, with a heap holding the current head of each run: take the smallest head, write it out, and refill that slot from its run, as the heap topic of Chapter 6 describes.

The data crosses the disk twice, once in each pass, and both times sequentially, which is the cheap way to use any disk. At disk speed, the reading and writing are nearly all of the cost; the comparisons hide underneath it. Databases do the same when a sort outgrows the working memory it is allowed. PostgreSQL, for one, switches to an external merge sort on disk when a sort exceeds its memory budget.

Lantern's AND: Merging Postings Lists

Each term in Lantern's index has a postings list, the sorted list of record ids that contain the term. A query with two terms asks for the records in both lists: the intersection of two sorted lists. Keep one pointer in each list. If the two ids are equal, keep the id and advance both pointers. Otherwise advance whichever pointer holds the smaller id, since that id cannot be in the other list.

That is merge sort's merge, keeping only the matches. It costs at most m plus n steps for lists of m and n ids, it sorts nothing, and it needs no memory beyond the two pointers and the output. An OR is the same walk keeping every id once, and a NOT walks one list while skipping the ids of the other. The sorting was paid for once, when the index was built.

When One List Is Tiny

A rare term with 50 postings joined to a common term with 400,000 costs up to 400,050 steps by walking both lists. Almost all of that is walking the long list past ids that cannot match. Looking each of the 50 ids up in the long list by binary search costs about 50 times 19, about 950 comparisons, because the base-2 logarithm of 400,000 is about 18.6. Measured on Python 3.15 with lists of those sizes, the walk took 394,387 steps and the 50 binary searches 944 comparisons.

Galloping comes close to the better of the two whatever the sizes: from the current position in the long list, probe 1, 2, 4, 8 places ahead until passing the target, then halve back. When the lists are similar in size it behaves like the walk, and when one is tiny it behaves like binary search. This is why a search engine intersects starting from its shortest list, so that the cost follows the rare term, not the common one.

What Sorting Costs in Lantern

Lantern never sorts at query time. Postings are sorted once, in the 02:00 rebuild, so at the Saturday peak of 300 searches a second each two-term query pays only a merge walk or a gallop. The 10 results on a page are the top 10 by score, kept in a heap of ten as Chapter 6 showed, not a sorted list of every match.

The costs that remain are the ones a sort hides. A key recomputed on every comparison instead of once per item multiplies the cost by the logarithm of n. And titles sorted by code point instead of by collation come out wrong. Measured on Python 3.15, sorting apple, Zebra, Émile and zebra gives Zebra, apple, zebra, Émile: every capital before every lowercase letter, and the accented É after z. Human alphabetical order is locale collation, a different and costlier key built on top of the code points of Chapter 2.