A heap of k run heads merges k sorted runs in one pass over the data. It makes more comparisons than merging the runs two at a time, not fewer — a sift-down examines both children — and what it buys is the pass count: one instead of k − 1. When the data lives on disk, a pass is the cost, which gives the external sort's pass formula; and the same runs-then-merges shape with insertion sort below a cutoff is what Timsort is.
Core ideas
The hard idea is that the cost model changes, and the algorithm that wins under the new one loses under the old.
Load the head of each of the k runs into a min-heap, then repeatedly extract the smallest and push the next item from the run it came from. Every item is popped once, so the whole merge is a single sequential sweep of all n items. Merging two runs at a time instead needs k − 1 rounds, and every round rereads the whole accumulated prefix: on eight runs of eight that is seven passes over the data against one.
This is the figure that surprises. On eight runs of eight, the heap merge makes 302 comparisons and the pairwise merges make 180. A two-way merge compares once per item taken; a sift-down compares the moved key with both children at every level, so the heap's count is about 2n log₂ k rather than n log₂ k. n log₂ k here is 192 and the measured 302 sits between that and 384, exactly as the extra child comparison predicts.
Sorting N records with M fitting in memory means writing N/M sorted runs and then merging them with a fan-in of M/B, where B is the block size, which gives 1 + ⌈log_(M/B)(N/M)⌉ passes. A billion records with a million in memory and four to a block takes two passes. The same billion with blocks of five hundred leaves a fan-in of two and takes twenty-one. Nothing about the comparison count changed.
The material
The k-way merge and its real comparison count, the external sort's pass formula, and the cutoff that makes a hybrid.
To merge k sorted runs holding n items in total: place the first item of each run into a min-heap of size k, tagged with the run it came from. Repeatedly extract the minimum, append it to the output, and insert the next item of that run. Each item is inserted once and extracted once.
The heap holds k items, not n, so the extra memory is the fan-in rather than the data. Each extract costs a sift-down of depth ⌊log₂ k⌋, so the order of the comparison count is n log k — but the constant deserves to be measured rather than assumed, and the lab measures it.
64 items. Through one heap: 302 comparisons, 64 pops, one pass over the data. Merging two runs at a time: 180 comparisons and seven passes, because each of the k − 1 rounds walks the whole accumulated prefix again. Both produce the same 64 items in the same order, and the lab checks that they agree rather than assuming it.
So in the comparison model the heap loses. n log₂ k = 192 at these sizes and the heap spends 302, which is between n log₂ k and 2n log₂ k = 384 — the extra factor being the comparison between the two children that a sift-down makes at every level before comparing with the parent. Heapsort paid the same factor in exactly the same place.
When N records do not fit in the M of memory available, sort in two phases. Run formation: read M records at a time, sort them in memory, write them back as a sorted run, giving N/M runs. Merging: repeatedly merge runs F at a time, where the fan-in F is M/B for a block size of B, since each open run needs one block of buffer.
Read the third line against the second. The data is the same size, the algorithm is the same algorithm, and the pass count went from four to twenty-one because the fan-in — the base of the logarithm — fell from 250 to 2. A pass over a billion records is the expensive thing here, and the comparison count does not appear in the formula at all.
That is why the heap wins on disk and loses in the lab's comparison column: it makes k runs into one in a single pass, so the number of passes is the logarithm of the run count in base F rather than in base two. System Design's “Sequential versus Random I/O” prices exactly this count — it is the same number of sequential passes over the same data — and nothing on this page depends on that pricing.
Merging singleton runs is wasteful: at the bottom of any merge sort the runs are tiny and insertion sort, which is Θ(m²) but with a small constant and no allocation, beats it there. A hybrid insertion-sorts blocks of size c and then merges them. On 64 shuffled keys the lab measures 594 comparisons at a cutoff of 1, 500 at 4, 448 at 11 and 527 at 20: the cheapest cutoff is strictly inside the range, which is what a crossover looks like.
Eleven is a measurement on one array, not a constant of nature. What generalises is the shape — form runs, insertion-sort below a cutoff, merge the runs — and that shape is Timsort's, which is the sort in the standard libraries of several languages. Timsort finds runs already present in the data rather than cutting fixed blocks, and merges them under a stack policy with galloping; neither of those is covered here.
Three figures on this page are of three different kinds, and the panel keeps them apart. 302 and 180 are comparison counts measured by running two merges on the same runs. 1 + ⌈log_F(N/M)⌉ is arithmetic: a count of passes over records, computed rather than measured, and refused outright when memory is too small to hold two blocks. And 11 is the low point of a curve sampled at twenty cutoffs on one array.
Interactive
One pass through a heap, against k − 1 passes over the data
Method
The first question is not which algorithm. It is what the cost model charges for.
In memory, a comparison. On disk, a pass over the data. The two rank the same two algorithms in opposite orders here, which is why naming the unit first is not pedantry: the heap merge makes 302 comparisons against 180 and is still the one to use.
Set k and the run lengths and read the two comparison columns, then the pass column. The heap's advantage is entirely in the last of those, and the lab checks that both methods produce the same merged sequence.
Runs are N/M, the fan-in is M/B, and the passes are 1 + ⌈log_F(N/M)⌉. Do it for two block sizes before choosing one; the block size enters only through the fan-in, and it is the base of a logarithm, which is where large changes come from.
If M/B is below two there is no merge to perform, and the lab refuses rather than returning a number. A formula that keeps producing pass counts for a configuration that cannot run is worse than an error.
Sweep the cutoff and read the total. The best value on the lab's 64-key array is 11; on another array it will be another number. Quote the shape as general and the number as local.
The runs are eight interleaved arithmetic sequences covering 1 … 64, so every run is sorted and no run dominates another. The two merges below are run on the same eight runs and produce the same 64 items.
The first table is the whole lesson in two rows. The heap loses the comparison column by 122 and wins the pass column by six, and which of those two facts is the cost depends on where the data lives. In memory the pairwise merge is the better choice; on disk seven passes over a billion records is not a choice at all.
The second table's third row is the one to keep. Same data, same memory, same algorithm, and five times the passes, because a block size of 500 leaves room for only two buffers and the fan-in is the base of the logarithm. The last row is the degenerate case worth checking a formula against: data that fits takes one pass and no merges at all.
For a faded rehearsal, work out the pass count for a hundred million records with ten thousand in memory and blocks of twenty. The supplied first move is the fan-in: M/B = 500. Compute the run count, then the logarithm, then the passes — and then say what block size would bring it down by one, and whether that is a change you could actually make.
You should be able to merge k runs through a heap by hand, explain why its comparison count is about twice n log₂ k, compute the pass count for given N, M and B and say what a change of block size does to it, and report a measured cutoff as the local number it is.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.