Pivot — where it appears
Named by 17 essays across 8 fields — each of them below, with the objects they name alongside it.
The words "on average" are not a number
Quicksort is Θ(n log n) on average. Six hundred runs at n = 512 give a distribution with a mean of 4,945 comparisons, a median of 4,908, and a worst case 32% above the mean. The average is a summary of that picture, it is the least interesting thing in it, and it is almost always the only thing reported.
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.
The constant the notation drops
Six algorithms on this site are Θ(n log n) and their comparison counts differ by a factor of two. The class is what they have in common; the constant is what distinguishes them. It is measurable to three digits, it is the number that actually decides between them, and it is precisely the number the classification is designed to discard.
The stack nobody counts
Merge sort makes 8,192 calls to sort 4,096 elements and holds fourteen of them at once. Depth-first search on a grid holds twelve vertices, or sixty-six, or a hundred and forty-four, depending on which of three equally standard implementations is running. The stack is a resource, it is the one that fails hard rather than slowly, and nothing that watches the data can see it.
What randomising the pivot buys
Quicksort taking the first element as its pivot costs 130,816 comparisons on an already sorted array of 512 — 27 times its cost on random data, and exactly the quadratic behaviour the algorithm exists to avoid. Randomising the pivot costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it unchoosable.
One run, four counts, four answers
The question “how many operations” has no answer until the operation is named. Selection sort makes more comparisons than any other algorithm here and fewer writes than almost all of them; bubble sort matches its comparisons and does 124 times the swapping. The ranking depends entirely on which count is chosen, and the choice needs justifying.
The frontier between time and space
The question of which sorting algorithm to use has an honest answer, and it is a shape rather than a name. Comparisons on one axis, peak auxiliary space on the other, and five of the ten algorithms here are on the Pareto frontier while five are dominated — beaten on both counts at once, so that no weighting of the two costs makes them the right choice. Heapsort is one of the five that lose.
The tree that is a list
A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.
Expected is not average
Quicksort on 2,048 sorted keys costs 2,096,128 comparisons with a first-element pivot and 25,318 with a random one. A binary search tree on the same keys is 2,047 deep; a treap is 26. A hash table on keys computed against its hash puts all 2,048 in one bucket; one drawn from a family puts at most 10 there. Three problems, one distinction.
In place is a claim, and it is usually wrong about quicksort
Heapsort holds one slot at its peak. Quicksort holds twenty-two at n = 4,096 on random input and 4,097 on a sorted one. Merge sort holds 4,110. All three are described with the same two words, one of the three descriptions is false, and the false one is the algorithm the phrase is most often attached to.
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 floor when the values repeat
log₂(n!) counts orderings of distinguishable things. Two hundred and fifty-six values drawn from eight distinct ones have 1,684 bits of permutation entropy and 739 bits of distinguishability, so the real floor is less than half the one every table quotes — and merge sort, which sits exactly on the quoted floor, is 2.3 times above the one that applies.
What derandomising costs
Randomised selection finds the median of twenty thousand elements in 3.21 comparisons per element and median-of-medians takes 8.15 — two and a half times as many for the same answer, both linear. The number that decides between them is not either of those. It is that the first varies by 28% from seed to seed and the second by 1.6%.
A search with no branch to miss
A binary search does about log₂ n comparisons and every one of them is a coin flip, so it mispredicts once per level. Writing it so the comparison feeds an index instead of a jump costs two thousand extra comparisons over two thousand searches and takes the mispredictions from 17,993 to 2,001 — flat in n, at every size. Under the counters this site had a phase ago, that is a strictly worse algorithm.
The adversary who knows the seed
Every randomised figure on this site is drawn from a stated seed, so that the numbers in the captions are the numbers on the reader's screen. That is also the exact condition under which none of the guarantees those figures demonstrate applies. A published seed is a published function.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
QuicksortGuaranteePartitionComparison countDistributionSwapsWorst caseCutoffIntrosortpdqsortRandomised algorithmRanking