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

Insertion sort — where it appears

A sort that takes each key in turn and moves it left past every larger key already placed, so its moves are the input's inversions. It is quadratic on a random input and linear on a nearly sorted one, which is why library sorts use it below a small cutoff.

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

32641282565121010010³10⁴elements sortedword operations a comparison must cost to break evenSelection sort, pairsSelection sort, closureBubble sort, pairsBubble sort, closureHeapsort, pairsHeapsort, closureQuicksort, median-of-three, pairsQuicksort, median-of-three, closuresolid: pairs asked · dashed: everything impliedrandom input · counted exactly

The price of remembering an answer

Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.

counting · Count 125102050100buffer, as a share of the filemoves a key of the file (log scale)1/41/161/641/2561/10241/4096pieces by insertionpieces by mergingmerge sort, whole tail65,536 keys, a late tenth from the top fifthmoves counted, sorted checked

Pieces that fit the buffer

A sorted file with a late tenth appended costs the buffer-limited stable merge sort 2.93 moves a key at a buffer of a 64th, fifteen times the least any sort could move, and two thirds of it is the tail sorting itself. Taking the tail a buffer at a time, inserting each key into a sorted piece in the buffer and merging the piece into the head, was predicted to bring that under two moves a key at small buffers. It never comes within twice the merge sort: insertion costs a quarter of a piece a key, and the smaller the pieces the more often each one's merge crosses the head's top fifth. The same pieces sorted in place by merging do pay, at 2.41 moves a key, and for a reason the proposal did not name: a piece that fits the buffer merges into the head without a single rotation. The gain lasts only while the tail belongs near the top of the file.

practice · Practice

Named alongside it

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

Honest limitAuxiliary spaceBreak-evenBubble sortComparison countCost modelData movementMeasured countMerge sortPartial orderPredictionRedundancy

All concepts