Equal elements — where it appears
Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.
The pattern that defeats the pattern
Quicksort's bad cases are patterns — sorted input, organ-pipe input, an adversary's construction. Introsort's answer is to notice the damage and switch algorithms. pdqsort's answer is to notice the pattern and break it, deterministically, with four swaps. On input with eight distinct values that turns a quadratic disaster into a linear sort, and the whole difference is one extra partition scheme.
The merge that can say equal
When two sorted lists draw their keys from a few values, equal keys can go on either side of each other, so far fewer answers are needed and the counting floor falls. Merging four keys into four over four values needs only 27 answers, not 70, and the floor falls from seven comparisons to five. A merge whose comparisons answer only 'at most' still needs seven on its worst input, exactly as many as distinct keys, because it can never learn that two keys are equal. A merge whose comparisons can answer 'equal' needs five and meets the floor. Solved exactly over every input, the third answer is the whole difference, and on average it is worth more than an optimal strategy.
The runs a short list cannot have
A merge whose comparator can say 'equal' meets the counting floor on lists of repeated values, but it takes the gain only when one list's head happens to meet an equal head in the other. Comparing keys inside a list would find runs of equal keys on purpose, and was predicted to leave the worst case alone and help a great deal on average when the values are few. Solved exactly at four keys a list, it leaves the worst case alone and helps by under a hundredth of a comparison: a list of four has no run worth finding, and an equal answer already places two keys at once. On long lists the same idea, galloping over each run before comparing across again, does pay — a twenty-sixth of the textbook merge's comparisons with one value at 1,024 keys a list — and at every length it stops paying at the same place: when a value's run averages fewer than about thirty-two keys a list.
A merge that decides per run whether to gallop
Merging two sorted lists of repeated values, a merge that gallops along every equal run beats the textbook merge while the runs average more than about thirty keys a list and loses below, a rule about the whole input. A merge that learns the runs as it goes was predicted to match the better of the two on uniform values and beat both on skewed ones. The proposal's rule — gallop when the last few runs averaged long — cannot learn a run that has not ended: at one, two or four values it walks every key. Timsort's own rule, applied to equal answers — walk until a bar of consecutive equal answers, then gallop, the bar moving by one as galloping pays or fails — does what was predicted. On uniform values it stays within a hundredth of a comparison a key of the better merge; under Zipf 1, at 4,096 keys a list and 1,024 values, it makes 0.447 comparisons a key against 0.595 walking and 0.594 galloping, a quarter under both.
A bar that wins rarely meet
A merge of two sorted lists of repeated values saves most of a textbook merge's comparisons by galloping along a run of equal answers once a bar of them have come in a row, with the bar lowered after a gallop that pays and raised after one that does not. Timsort keeps the same kind of bar for the other kind of stretch, one list winning repeatedly, and a merge of repeated values meets both. One count and one bar for either kind was predicted to save a further tenth under Zipf 1 and change nothing on uniform values. It saves at most 1.0% under Zipf 1, costs up to 1.3% on uniform values, and two separate bars do no better. In two lists drawn from the same distribution a stretch of wins long enough to gallop over is rare: under Zipf 1 at most 18% of the shared bar's gallops are over wins, and where wins dominate the gallops, at a thousand uniform values, the runs of either kind are too short for any gallop to pay.
Named alongside it
The objects these essays reach for when they reach for this one.
Average caseComparison countMerge sortGallopingExhaustive searchHonest limitInformation floorPredictionZipf distributionAdversary argumentBad partitionDecision tree