Concept

Equal elements — where it appears

Keys that compare equal, so that no order between them is required in a sorted output. They lower the number of outcomes a sort or merge must distinguish, but a comparison can exploit them only if it can report equality rather than just less-than.

Named by 2 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.

practice · Practice

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.

floors · Floor

Named alongside it

The objects these essays reach for when they reach for this one.

Adversary argument Average case Bad partition Comparison count Decision tree Depth limit Deterministic shuffle Exhaustive search Guarantee Honest limit Information floor Introsort

All concepts