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

External merge sort — where it appears

Sorting data too large for memory by making sorted runs and merging them, in a number of passes set by the memory and the block size. Its pass count is set by the memory and the block size, so its cost is a step function of two parameters rather than a smooth curve.

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

10³10⁴10010³n (elements)block transfersM = 256 · fan-in 7M = 1024 · fan-in 31B = 32, M as labelled4 passes against 3

Sorting what will not fit

Merge sort's Θ(n log n) is a statement about comparisons and says nothing about a file larger than memory. Counted in transfers the answer is (n/B)·log_{M/B}(n/B), and the base of that logarithm is the number of blocks that fit in memory — so doubling the memory does not halve the work, it moves a staircase. The measured cost jumps by 32,768 transfers at one step and by nothing for the next four.

applied · Transfer 10⁴10010³n (elements)block transfersmeasured sortthe bound3.20×2.67×2.29×2.94×2.67×2.40×B = 32, M = 512 (M/B = 16)3.20× the floor at worst

The floor under moving data

The information-theoretic floor for comparison sorting is log₂(n!) and it says nothing about a file on a disk. In the external model the floor is (n/B)·log_{M/B}(n/B), it is a bound on every algorithm rather than on merge sorts, and a measured external sort sits 2.40 to 2.97 times above it. Both numbers are computable, and the gap between them is what a real implementation costs.

floors · Floor 1010010³10⁴B — elements to the blockblock transfersthey cross near B = 4one element at a timesorted by destination, 2passesM = 4,096, B as drawnthe lower bound is the smaller of the two, and it is proved rather than measured

Permuting is the harder problem here

Rearranging 65,536 elements into a stated order costs 63,601 transfers one at a time and 4,096 by sorting them into place. In the model every other field on this site uses, the first is the cheap method and beats the second by a factor of eight. The two models disagree about which problem is easy, and they disagree by about the same factor in opposite directions.

applied · Transfer 1×10×10³10⁴the key side, as a multiple of memoryblock transfersblock nested looppartitioned hash joinsort–merge joinB = 64, M = 512 (M/B = 8)the other relation: 16,384 rows

Two ways to join, and the ratio that decides

The same join costs 260 transfers one way and 1,040 the other; at eight times the memory the same two costs are 2,880 and 1,280, the other way round. Neither number is a property of how large the tables are. The quantity that decides is how the smaller of them compares to memory, and a rule of thumb phrased in rows is a rule about somebody's machine.

applied · Transfer 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.

Block transferExternal-memory modelRegimeScanCost modelComplexity classFan-inLower boundMerge policyTrade offAdaptive sortCounting argument

All concepts