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

Inversions — where it appears

The pairs of elements a sequence holds in the wrong relative order, from none when sorted to every pair when reversed. Insertion sort does one step of work per inversion, which makes the count the right measure of disorder for it and the wrong one for costs that do not grow with distance.

Named by 3 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 10⁵10⁶10⁷10³10⁴inversions in the permutationblock transfers to carry it outsort by destination, 1,536w 8w 32w 128w 512w 2048w 819216 swaps64 swaps256 swaps1024 swapsshuffled inside windowsa few pairs swapped farn = 16,384, B = 64, M = 512 (M/B = 8)inversions do not order the cost

The permutation that moves almost nothing

Two ways to scramble sixteen thousand elements. Shuffling them inside windows of five hundred and twelve puts two million pairs out of order and costs 3,095 block transfers to carry out. Swapping a thousand pairs across the whole array puts seven million out of order and costs 1,189. Inversions are the textbook measure of disorder, and on a disk they rank these two backwards.

applied · Transfer 0.0010.010.11125102050fraction of positions reshuffled, pmean comparisons, in multiples of the mean on random inputFirst-element quicksort, 81.9×Median-of-three quicksort, 41.4×Insertion sort, 2.0×Merge sort, 1.0××: unshuffled2,048 elements · 12 shuffles a point1 = the mean on random input

A worst case ten positions wide

Sorted input costs first-element quicksort 2,096,128 comparisons on 2,048 elements, 82 times its average. Reshuffle about eleven of the 2,048 positions and the cost halves — and it takes about ten at 128 elements, and between ten and thirteen at every size between. Reversed input costs insertion sort twice its average, and reshuffling half the positions still leaves 71% of the work. A worst case is a place in the space of inputs, and the two famous ones are places of very different sizes.

counting · Count

Named alongside it

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

PresortednessPermutationAccess patternAdaptive sortAdversarial inputBenchmark inputBlock transferCacheCrossoverDisplacementDistributionExhaustive search

All concepts