Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Depth limit — where it appears

The recursion depth past which a hybrid sort abandons its partitioning and falls back, chosen so that it fires only under attack. It is chosen so that it fires only under attack, which means a correct implementation almost never executes the branch that provides its guarantee.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

algorithmspread of count ⁄ f(n) — 1.0 is exactTimsortPython, Java objects, Rust, Android1.176nIntrosortC++ std::sort1.104n log nPattern-defeating quicksortRust unstable sort, Boost, libstdc++ 141.155nDual-pivot quicksortJava Arrays.sort, primitives1.624no class grantedtolerance 1.6fitted n = 256–16,384comparisons, counted exactly

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 1010010⁵minruncomparisonsshipped: 32randomnearly sortedTimsort, n = 8,192comparisons; rings mark the measured minimum

The threshold somebody chose

A minrun of 32. An insertion cutoff of 16. A gallop threshold of 7. A depth limit of twice the logarithm. Four numbers, in four real source files, none of which appears in any complexity analysis — and each of which decides more about what these algorithms do than the analysis does. Swept, they turn out not to be optima, and finding out what they are instead is the point.

practice · Count 10³10³10⁴10⁵10⁶10⁷ncomparisonsadversary, no depth limitadversary, as it shipsrandom inputn²/2McIlroy's adversary, answering as it goescomparisons, counted exactly

The depth limit that almost never fires

Introsort counts how deep its recursion has gone and calls heapsort if it passes twice the logarithm. On every input measured, the mechanism handles under a tenth of a per cent of the elements. Then an adversary that answers the comparisons rather than choosing the array drives it to exactly n²/2 with the limit removed, and to one heapsort call with it — a factor of forty-two at n = 8,192, and growing.

bounds · Bound

Named alongside it

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

IntrosortQuicksortGuaranteePartitionpdqsortPivotRecursion depthThresholdAuxiliary spaceBad partitionComparison countCutoff

All concepts