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

Adaptive sort — where it appears

A sort whose cost falls on input that is already partly ordered, with the bound stated in a measured disorder parameter rather than in a named input kind. Its bound is stated in a measured disorder parameter, and two such parameters can disagree about which of two inputs is more ordered.

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

11010010³10⁴10⁵10⁶10⁷natural runs r in the inputcomparisonsn / minrun = 256TimsortMerge sortInsertionn + n log₂ rn = 8,192, runs built exactlycomparisons, counted exactly

A run is a property of the input

A benchmark that says "nearly sorted" never says how nearly. It is a recipe with a seed, not a measurement, and an adaptive bound stated against it is a bound with an undefined second parameter. Counting the natural runs turns the shape of an input into a number — and then Timsort's bound becomes something that can be fitted rather than quoted.

practice · Practice dark: with galloping · pale: with the mode removednearly sorted33,95221,373 jumped−37.7%few distinct values57,91241,178 jumped−36.9%random95,7702 jumped+0.0%n = 8,192, MIN_GALLOP = 7comparisons, counted exactly

When galloping pays

Timsort's merge does not always take elements one at a time. When one run has won seven times in a row it switches to searching for how many to take at once, and switches back when that stops paying. The mode saves 22,104 comparisons on nearly sorted input, 33,270 on input with few distinct values, and costs exactly six on random input — which is the whole design in three numbers.

practice · Practice the language's sortMerge sortlog₂(n!)random43,810 / 43,976nearly sorted10,806 / 24,845already sorted4,095 / 24,576reversed4,095 / 24,576few distinct values27,561 / 42,338n = 4,096, counted through the comparatorthe first column is a fact about the engine, not about sorting

The count that came from somewhere else

Every count in these essays is described as exact, reproducible, and identical on every machine. Two of them are not. A spanning-tree measurement quotes 42,385 comparisons spent in a sort, and that sort is the language's own — whose comparison count is specified nowhere, varies by a factor of thirteen across input kinds, and comes within one per cent of the information floor on random input.

counting · Count 1M2M4M16M64Mmean run length, in memoriesrandom33 runssorted1 runreversed64 runssorted, 1% arriving late2 runssorted, 10% arriving late7 runs262,144 records, 4,096 in memorydashed: two memories

Runs twice as long as memory

Feed 262,144 random records through a heap that holds 4,096 and the sorted runs that come out average 1.94 memories — the snowplow's famous factor of two. At a fan-in of 63 that saves a merge pass at 262,144 records, and at two of fourteen sizes in all. Feed the same heap a sorted file with one record in a thousand out of place and it writes two runs instead of sixty-four. And it spends 19 comparisons a record doing so, on every input, where sorting the chunks spends five on sorted data. The factor of two is the least of what the method does.

applied · Transfer

Named alongside it

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

TimsortComparison countMerge policyPresortednessBinary searchBlock transferDeterminismExponential searchExternal-memory modelExternal merge sortFailure modeFan-in

All concepts