Sorting when the input does not fit
An in-memory comparison count is not enough to describe a sort of a file larger than working memory. The algorithm must also bring blocks from storage into memory and return results. Sequential transfers can be much cheaper than many scattered accesses, but a complexity count is useful only after we specify what a transfer contains and what is stored between passes.
Definition 20.1.1
(Block-transfer model)
A fixed finite input file of records occupies exactly blocks of records. A block transfer reads or writes one full block. Working memory holds record slots, with . Keys have a total order, and records have a well-defined original order. The cost of an algorithm in this model is its number of block transfers.
Small per-run descriptors and counters are accounted for separately. We count block transfers, not elapsed time, comparisons, physical seeks, or metadata traffic. A block is a unit of transfer, not an assumption that all storage devices have the same latency.
Definition 20.1.2
(Run)
A run is a contiguous sorted sequence of records stored as whole blocks.
Here every run contains an integral number of full blocks. This convenient condition follows from our input size and construction; a real partial last block can be padded with a valid-record count, which must not be mistaken for data.
Generate and merge runs
Put and . Since , we have and .
- Read at most blocks, stably sort those records in memory, and write the sorted chunk as one run. Stable merge sort can use a second array of the same size; record slots suffice. Continue until all blocks have been consumed. Thus there are initial runs, in the original chunk order.
- In a merge pass, group consecutive runs into groups of at most . For each group, reserve one block buffer per input and one output buffer. Repeatedly select the smallest current head, emit it, refill an input buffer only when exhausted, and flush the output buffer when full. Resolve equal keys in favor of the earlier input run; within a run preserve its order. Write the result as one new run. Even a group of one is copied in this stated pass.
- Repeat passes until one run remains. If , no merge pass is needed. A pass operates on the complete output of the previous pass; the original and output storage must be available until the pass finishes.
The input buffers plus output buffer require at most record slots. A heap or tournament tree of at most run heads needs additional descriptors; these are not included in the record slots. In an implementation with a strict byte budget, reserve space for them first and recompute the feasible fan-in. The selection structure must also distinguish an exhausted run from a record with a legitimate maximum key.
Common mistake
(Giving all memory to input buffers)
It is tempting to merge runs at once. Those input buffers plus one output buffer would need slots, and by the definition of the floor , so this always exceeds memory. With and , four input buffers and an output buffer need slots. The fan-in reserves the output block explicitly.
Theorem 20.1.3
(Correctness and stability)
Under the assumptions and procedure above, every run produced is a stable sorted permutation of a consecutive interval of the input, and the final run is a stable sorted permutation of the whole input.
Proof
(Induction over passes)
Initial runs are sorted stable permutations of consecutive input chunks, and they appear in the original chunk order. Consider a merge group whose input runs are stable sorted permutations of consecutive original intervals, listed in the order of those intervals. Every unconsumed element of a sorted input run is at least its current head, so the smallest head is a smallest remaining element of the group. Emitting it and repeating produces a sorted permutation, without losing or duplicating any record. For stability, take two records with equal keys. If they come from the same run, that run's order is kept and it is already the original order. If they come from different runs, the record from the earlier run originally precedes the other, because the runs cover consecutive intervals in order; the tie rule emits the earlier run first. Consecutive runs represent consecutive original intervals, so the merged run does too. Induction establishes the claim for every pass and ultimately the final file.
The induction carries more than sortedness, and that extra information is what the tie rule needs.
Proof X-ray
Why local tie rules preserve global order
Sortedness alone is closed under merging, but stability is not: it needs to know where each record came from. The proof therefore carries a stronger invariant, that each run is a stable sorted copy of a consecutive interval of original positions and that runs are kept in interval order. The key move uses this invariant once. Among equal keys from distinct runs in the same group, every record in the earlier run originally preceded every record in the later run, so a purely local rule, prefer the earlier input run, preserves the global original order. The smallest-head argument uses only that each input run is sorted; the stability argument uses that groups are formed from consecutive runs in order. Grouping nonconsecutive runs would keep sortedness but could break stability.
Theorem 20.1.4
(Pass count and transfer count)
With for (so when ), the run generation and all merge passes perform exactly
block transfers in this abstract model. Temporary storage can be reused between passes, but this count includes writing the final run.
Proof
(Count runs, then blocks)
If a pass starts with runs it produces . Repeated ceiling division yields after passes: both sides equal the least integer for which . Therefore the first with one run is . Run generation reads and writes each of the blocks exactly once. In each merge pass, every input block is read once and every output block written once; group sizes are whole blocks and no record is discarded. There are again exactly output blocks. Summing the initial and further costs of proves the formula. This is an accounting identity for this procedure, not a lower bound for every possible sorting algorithm.
Concept lensCombinatorial
The passes as levels of a merge tree
Draw each initial run as a leaf and each merge group as a node whose children are the runs it consumes. Pass is then level of a rooted tree in which every node has at most children and level has nodes; the root is at height . Because a singleton group is still copied, every leaf lies at depth exactly . Each level rewrites all blocks once, so the merge passes cost transfers: the pass count is the height of this tree.
Common mistake
(Forgetting the run-generation pass)
The count is , not : run generation reads and writes every block once before any merge begins. For the six-block example below, , whereas the procedure performs transfers. When the merge term vanishes but the sort still costs .
Worked example 20.1.5
(Three runs, one pass)
Let , , and let the twelve input keys be
Here , , , and . Stable in-memory sorts produce , and . One three-way merge gives . The first 5 precedes the second because its original chunk precedes the third. The initial pass reads six blocks and writes six; the merge does the same, for 24 transfers. If the final sorted stream is consumed directly rather than written, a different output contract and a different count apply.
The pass count grows only logarithmically in the number of runs, but each pass costs a full read and write.
Worked example 20.1.6
(Ten runs, three passes)
Let , and . Again and , so , nine runs of two blocks and one of a single block. The first merge pass groups the runs as and produces four runs; the singleton group is copied, as the procedure states. The next pass groups and produces two runs, and the third produces one. Successive counts are , hence , since . The procedure transfers blocks.
At the other extreme no merge is needed at all.
Worked example 20.1.7
(A file that fits in one run)
Let , and . Then , so the whole file is read as one chunk, sorted stably and written: and . Run generation reads two blocks and writes two, a total of transfers. The formula still counts the write of the final run, which is part of the output contract.
Counterexample mode
Sorted chunks do not imply a sorted file
Claim: once every chunk is sorted, writing the runs one after another gives a sorted file. The concatenation of runs and is not sorted: precedes . Nor is choosing an arbitrary input on tied keys stable. If the earlier run contains and the later one , emitting first reverses the original order. Correctness needs the smallest-head merge and stability needs the earlier-run tie rule; they require separate arguments.
What the bound does and does not predict
A binary heap gives head-selection work per emitted record, so the merge comparison work is , with comparisons for stable in-memory run sorting. Reading a block, however, can cost very different amounts on different devices; the transfer bound alone is not a runtime benchmark. Compression, variable record sizes, parallel disks, asynchronous prefetch, operating-system caching and failures are outside this model. A larger fan-in can reduce passes while increasing buffer and descriptor pressure. Retrying a failed pass also needs a separate atomic-output and recovery contract; an incomplete output must not be treated as a completed run.
Practice with solutions
Quick check
(Two sorted input runs have keys and , with the first run earlier in the original file. Give their stable merge.)
Apply the tie rule whenever the current heads are equal.
Solution · Answer
The order is ; the two 4s from the first run occur before the 4 from the second, and preserve their internal order.
Quick check
(Let , and . Find , , , and the number of block transfers.)
Compute and from the definitions, then iterate the ceiling division.
Solution · Answer
and , so . Since , ; the run counts are . The procedure transfers blocks.
Quick check
(With and , what is the smallest integer for which at most one merge pass is needed?)
One pass suffices exactly when .
Solution · Answer
We need with and . For : , , . For : , , . For : , , . For : , , , so . The answer is , with transfers.