Dominance — where it appears
Named by 4 essays across 4 fields — each of them below, with the objects they name alongside it.
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 count somebody chose
Six quantities can now be measured for every sort. Ranking the ten algorithms by each of them and comparing the orders, comparisons and peak space disagree about 91% of all pairs, and memory traffic and modelled misses disagree about 7%. There is no ranking of sorting algorithms; there are six, and choosing between them is a statement about the data rather than about the algorithms.
A register that became a list
HyperLogLog replaces a key per distinct item with a five-bit register, and over a whole stream that is a saving of a hundred times. Ask it about the last four thousand arrivals instead and the same comparison against the same exact structure comes out at five. The estimator did not get worse. The exact answer got cheap.
The shape one structure will not fold
Folding thirty-two shards largest-pair-first keeps 2,556 quantile tuples against a balanced tree's 3,211 — a fifth of the space saved. The same fold on the counter tables beside them leaves 403 counts of error against the tree's 148. A deployment holding both cannot fold once and be right twice.
Named alongside it
The objects these essays reach for when they reach for this one.
Trade offPareto frontierCacheMeasurementQuicksortRankingState bitsAlgorithm selectionAuxiliary spaceCardinalityCost modelDistinct count