What the libraries do
The sort the library ships
What a standard library actually runs, measured with the same instrument as everything else here — and why a library sort is a policy with thresholds rather than a procedure with a complexity.
A run is a property of the input
Turning the shape of an input into a measured number, so an adaptive bound has a second parameter that can be swept — and finding the point where the input's structure stops mattering.
When galloping pays
How Timsort's galloping mode works, what it saves, what it costs when it cannot help, and why a mode entered on evidence is safe to have switched on everywhere.
The pattern that defeats the pattern
How pattern-defeating quicksort detects a bad partition and responds, why its equal-element partition makes it linear on duplicate-heavy input, and what an omission in the implementation nearly reported as a property of the algorithm.
The threshold somebody chose
Sweeping the constants inside real library sorts, finding that none of them minimises any single counter, and working out what they are actually chosen against.
The dictionary that builds itself
LZSS and LZ78 measured — what a dictionary coder's model actually is, why the window has an optimum rather than growing without limit, and what a compressor does on a stream with nothing to find.
The fading nobody computes
Why an exponentially decayed counter is computed lazily, what the laziness costs at the one operation that cannot be lazy, and where floating point forgets faster than the decay does.
Sized for a rate that does not hold still
What a capacity chosen from mean occupancy actually delivers on a stream whose rate varies, why overflow and idle space cannot both be made small, and where the headroom that fixes one stops being worth paying.
The rule that pays on a long enough text
Adding a matcher's preprocessing to its scan, and finding that which shift rule is cheaper is a question about how much text there is.
Where the exact rules pay now
The precomputation-plus-scan arithmetic for two multi-pattern shift rules, redone once the exact rules are built from the trie's links rather than from their definition.
The number that would choose a cap
The measurement that decides a depth cap, why it costs nothing, and what a parameter chosen from a curve rather than from the data actually costs.
What the generated collection was right about
The accounting across five strands — which conclusions transfer to real documents, which were properties of the generator, and what a model is and is not for.
The crossing that never arrives
The listing crossing measured on two real collections of the same prose cut two ways, and what occurrences-per-document has to be before a structure proportional to the answer is worth its bits.
The cap that would ship
The cap sweep re-run on real text, the knee measured on collections nobody generated, and what a system indexing a version history should set the parameter to.
The saving, spent
The asymmetric index at equal size to the symmetric one, with the forward sampling made four times denser, and what that does to the LF steps a locate costs.
The apparatus that is smaller than its index
The document-listing apparatus priced in three stages, what remains once the chain is gone, and which collection shapes the whole structure is worth building for.
A collection is a construction
Two constructions of one repetitive collection, measured against each other on every quantity this field charges for, and what a corpus description has to say to be usable.
The smaller tree hands it back unsorted
The one remaining choice in a document-listing apparatus, priced in both directions, and the case where an ordering preference becomes a correctness question.
A looser budget wastes a larger share
The dead-extension share swept over the error budget, and why a pruning's value rises rather than falls as the problem gets harder.
The floor was the marks
A published saving retracted by replacing a component, and what a curve that flattens is usually telling a reader.
The saving that is a loss
The interval enumeration measured on a search that does not branch, and why two operation savings split by the shape of the query rather than stacking.
The scan the order does not touch
The other half of a phrase index's propagation, attacked by a structure rather than by an ordering, and why the two are kept on separate plates.
Where the table starts paying
The construction cost of a deterministic machine against the per-character cost of a non-deterministic one, and the text length at which the table becomes worth building.