Runs twice as long as memory

Sorting what will not fit priced merge sort on a file larger than memory, and found that its cost was not a smooth curve but a staircase. The sort reads memory-sized chunks, sorts each, writes it back as a run, and then merges runs in groups as large as memory can hold one block of each — a fan-in of $M/B - 1$. Each merge pass reads and writes the whole file, so the cost is the number of passes times $2n/B$ transfers, and the number of passes is a logarithm to the base of the fan-in. Doubling memory did not halve the work; it moved a step.

Every run in that sort was exactly one memory long. That is a choice, and the classical alternative makes longer runs from the same memory. Replacement selection keeps a heap of $M$ records instead of a buffer. It repeatedly writes the smallest record that can still extend the current run, reads the next record from the input into the space that frees, and marks the new record for the next run if it is smaller than the one just written — because a run must stay in order, and that record arrived too late to join it. When no record in the heap can extend the current run, the run ends and the next begins.

The textbook claim is that on random input these runs are twice as long as memory. This page checks the claim, and then asks the two questions that decide whether anybody should care: what a factor of two in run length buys at a realistic fan-in, and what the method does on input that is not random.

What the heap makes of five orders #

The five bars span a factor of sixty-four, and the two methods agree on exactly one input.

On random input the claim holds. Thirty-three runs from 262,144 records, 1.939 memories each on average, against sixty-four runs of one memory for the chunk method. The small shortfall from two is the first and last runs, which the next plate isolates.

On sorted input the heap never has to start a second run. Every record read is larger than every record written, so each one joins the current run, and the whole file comes out as one run of sixty-four memories. The chunk method sorts sixty-four chunks that were already sorted and hands the merge sixty-four runs to put back together.

On reversed input the two methods agree. Every record read is smaller than every record already written, so every one is marked for the next run, and each run ends exactly when the heap has emptied of the records it started with — one memory. This is replacement selection’s worst case, and it is no worse than the chunk method. It cannot be worse: when a run begins, every record in the heap belongs to it, because the previous run ended precisely when no record of that run remained, so every run but the last holds at least the $M$ records it started with.

On a sorted file with late arrivals the heap absorbs most of the disorder. When one record in a hundred arrives at a random later point, the file comes out as two runs; one in ten, seven runs of about nine memories. A late record is marked for the next run only if the current run has already passed its value, and in a file that is mostly in order that happens rarely.

Why two #

The middle runs sit on two with a spread of a few per cent either way, and the first and last are the visible exceptions — which together are exactly why the mean is 1.939 rather than two.

The classical explanation, Knuth’s, is a snowplow on a circular track in steady snowfall. The plow is the point up to which the current run has been written; snow that falls ahead of it will be cleared on this lap, snow that falls behind it waits for the next. The heap holds all the snow on the track, which is $M$ records. In steady state the depth of snow rises linearly from just behind the plow to just ahead of it, because the snow just ahead has been falling for a whole lap and the snow just behind has only just begun, so the average depth is half the depth in front of the plow. The plow clears the full depth in front of it on every lap, which is twice the average — twice the $M$ records on the track.

The analogy explains the first run too. It starts with an empty track rather than a steady one: the heap is filled once from the input and none of it is yet behind the plow, so the first lap clears less than a full steady lap would. The last run is whatever is left when the input runs out, and has no reason to be any particular length.

What the factor buys #

A run twice as long halves the number of runs, and the question for an external sort is whether halving the runs removes a merge pass. A merge pass removes a factor of the fan-in; halving removes a factor of two. So halving saves a pass only when the number of runs was just above a power of the fan-in and falls to just below it.

Two sizes in fourteen, and the pattern is close to exact. With a fan-in of 63, the number of passes steps up when the number of runs passes 63, then 3,969, then 250,047 — and runs about twice as long move each step to a file about twice as large. So replacement selection saves a pass in a window roughly a factor of two wide at the bottom of every step, and each step is a factor of 63 wide. On a logarithmic scale of file sizes that is about $\log 2 / \log 63$ of the axis, a sixth.

The smallest size is where “about” matters. At 8,192 records the chunk method makes two runs and one merge pass, and a factor of two would make one run and none. The measured heap makes two, because its first run is short — 1.73 memories on the earlier plate rather than two — and a file only two memories long is almost all first run. The saving the snowplow promises is a steady-state saving, and a small file never reaches the steady state. The plate is drawn from measured runs wherever a measurement is affordable, and above a million records, where it takes runs to be two memories, the checks confirm that a shortfall to 1.9 memories would change no pass count.

Inside those windows the saving is large. At 262,144 records a pass reads and writes the whole file, 8,192 transfers, and going from two merge passes to one removes a third of the sort’s transfers. Outside them the saving is nothing at all. The flat bottom of a shallow curve found the same shape in a tuning constant: a quantity that changes the answer only near its boundaries, and whose value is therefore mostly a question of which side of a boundary the workload falls on.

The fan-in is why this matters so little. At 63 a single merge pass handles 63 runs, which is 258,048 records of one-memory runs, and three passes handle 250,047 runs — a billion records. Sorting what will not fit used a much smaller fan-in to make its staircase visible; at realistic block and memory sizes nearly every file needs one or two passes, and doubling the run length changes that count only near the edges.

What the method does with order that is already there #

This is where the method earns its place, and the factor of two is the far right-hand end of it.

A sorted file with one record in a thousand displaced comes out as two runs, merged in one pass; the chunk method makes sixty-four runs and needs two. Displace one in twenty and there are still only four. Displace a quarter of the file and there are fifteen runs of more than four memories. Only a file shuffled through completely brings the runs down to the snowplow’s two memories.

The disorder model here is the one a worst case ten positions wide used to measure how fast a worst case decays — mark each position with some probability and shuffle the marked values among themselves — and it measures the same kind of property from the other side. There, a little disorder destroyed an expensive input. Here, a little disorder barely disturbs a cheap one, because replacement selection’s cost depends on how often a record is smaller than the one just written, and a mostly sorted file rarely offers one.

That makes replacement selection an adaptive run former, in the sense a run is a property of the input gave the word for in-memory sorts: its output depends on how much order the input already has, and the chunk method’s does not. Data that arrives nearly sorted — an append-only log with a few late records, a table clustered on its insertion time, the output of a previous sort with a batch of updates — is exactly the data an external sort is most often asked to sort, and it is the data on which the difference between the two methods is largest.

What the heap costs #

None of this is free, and the price is paid in comparisons rather than in transfers.

The heap spends about nineteen comparisons a record on every input, and the reason is its construction. Every record read is pushed into a binary heap of a thousand and some records and every record written is popped from it; a push compares upwards through about $\log_2 M$ levels, a pop compares downwards against both children at each of $\log_2 M$ levels, and whether the input is sorted, reversed or random changes neither path length much. Nineteen is almost exactly $2 \log_2 M$ less a little, which is what those two operations cost between them.

The chunk method spends 8.73 comparisons a record on random input — a merge sort of a thousand records makes about $\log_2 1024$ comparisons per record less a constant — and five on sorted or reversed input, because a merge whose two runs do not interleave stops comparing as soon as one is used up. So on random input the heap spends more than twice the comparisons of the chunk method, and on sorted input nearly four times.

That reverses the usual description of the two methods in an instructive way. Replacement selection adapts its runs to the input and spends the same comparisons on every input. The chunk method with a merge sort adapts its comparisons to the input and makes the same runs on every input. Each is adaptive in one currency and oblivious in the other, and on sorted data the heap buys sixty-three fewer runs with fourteen extra comparisons per record. The count somebody chose found that ranking sorts by different counts gives different orders; these two methods rank the other way round on sorted input depending on whether comparisons or runs are counted.

Which currency matters is a question about the machine. When the file is far larger than memory, a merge pass is 2n/B transfers and a transfer costs orders of magnitude more than a comparison, so runs are the currency and the heap’s extra comparisons are noise. When memory is large enough that the whole sort takes one merge pass whatever the runs, the pass count is fixed and the comparisons are the only difference between the methods — and then the chunk method is cheaper by a factor of two to four. The heap also touches its array in the scattered pattern where an algorithm looks showed a heap has, which a cache charges for, and the chunk method’s merges are sequential sweeps it does not.

The reading and writing of run formation itself is a single sequential scan of the input and a sequential write of the runs either way. What differs between the methods is what they hand the merge — how many runs, and how long — and what they spend in memory deciding it.

Why the runs are built rather than found #

It is worth being precise about what the heap does on the nearly sorted files, because it is not what a sort that looks for runs does.

A file sorted except for one record in a hundred arriving late has a descent — a record smaller than the one before it — at nearly every late record, so it holds about 2,600 descents in 262,144 records and the same number of natural ascending runs. A run is a property of the input measured Timsort on exactly that property: a sort that finds natural runs and merges them does work proportional to how many there are. Replacement selection writes two runs from the same file. It is not finding the file’s runs, which are thousands; it is building runs of its own, using its memory as a buffer that holds a late record back until the output has caught up with it, and only a record that arrives after the output has passed its value — later than a whole memory’s worth of records — forces a new run.

That is also why the method needs a heap rather than a sort. At every step it must write the smallest record that can still extend the current run, from a set of records that changes by one on every step; that is a priority queue’s job, and a priority queue on $M$ items costs about $\log_2 M$ comparisons an operation whatever the order of what goes in. The chunk method can use any sort, including one that notices a chunk is already in order, and the plate above shows a merge sort doing exactly that. A replacement selection that noticed when its input was running in order — and wrote records straight through without pushing and popping them — would combine the two methods’ advantages, and nothing on this page measures whether its bookkeeping would cost less than the comparisons it saved.

What the model leaves out #

The merge treats all runs as equal. A merge of 63 runs at a time is charged for reading and writing everything, whatever the runs’ lengths. Replacement selection on real data produces very uneven runs — the plates show a first run shorter than the rest and a last run of 0.45 memories on random input, and on nearly sorted input a few enormous runs beside a small one — and a merge that paired runs by size could do better than one that takes them in the order they were written.

Records are integers, and equal keys are rare. A heap with many equal keys still writes them into the current run, since a key equal to the last one written does not break the order, so duplicates make runs longer rather than shorter. The plates do not measure how much.

Memory is a count of records. A real heap holds variable-length records, and a heap that holds pointers into a buffer uses some of its memory on the pointers — which shortens every run by the fraction spent on bookkeeping.

Still open: merging runs that are not the same length #

The merge on this page, and on sorting what will not fit, takes runs in groups as they come. When the runs are equal that is optimal. When they are not — and replacement selection makes them unequal by construction on exactly the inputs where it helps most — merging the shortest runs first saves reading the longest ones repeatedly, in the way a Huffman code saves bits by merging the least frequent symbols first. The fold that minimises the wrong thing measured a version of that problem for summaries rather than files and found that the order of combination changes more than the cost.

The measurement that follows prices a size-ordered merge against the one on this page, on runs from replacement selection over random, nearly sorted and late-arrival inputs, and asks how many transfers merging by size saves, and whether on nearly sorted data — where one run holds almost everything — the right merge is not a merge at all but an insertion of the small runs into the large one.