Fan-in — where it appears
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Block transferExternal-memory modelExternal merge sortMerge policyRegimeAdaptive sortComplexity classCost modelHeapPresortednessScanStaircase