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

pdqsort — where it appears

Quicksort with bad-partition detection and a deterministic shuffle in response, which keeps the average case while removing the adversarial one. Its response to a bad partition is a deterministic shuffle rather than a coin, so it keeps reproducibility and removes the adversarial case anyway.

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

Timsort95,770shipsIntrosort130,863shipspdqsort114,408shipsDual-pivot116,836shipsMerge sort96,145textbookHeapsort187,796textbookQuicksort, median-3119,098textbookalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly

The sort the library ships

Every sorting algorithm measured on this site so far has one thing in common — none of them is what runs when a program calls sort. Python, Java, Rust and Android run Timsort; C++ runs introsort; Java's primitive sort is dual-pivot quicksort. Not one of the four was in this collection, and the reason it matters is that they are not algorithms in the sense the other essays use the word.

practice · Practice 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 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 Dual-pivot116,836shipsIntrosort130,863shipspdqsort114,408shipsTimsort95,770shipsalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly

Two pivots and what they cost

Java changed its primitive sort in 2011 on the strength of an analysis showing dual-pivot quicksort does fewer comparisons than the classical one. It does. It also does nearly twice the swaps, and the analysis that decided the matter counted neither — it counted a weighted combination that had to be chosen before any conclusion could be drawn.

counting · Count

Named alongside it

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

IntrosortPivotQuicksortPartitionSwapsCutoffDepth limitGuaranteeJavaLibrary sortRecursion depthThreshold

All concepts