Pieces that fit the buffer

The moves no stable sort can skip set the buffer-limited stable merge sort against a floor: a key that starts out of place must be written at least once, and with one spare cell each cycle of the permutation costs one more write. On a sorted file of 65,536 keys with a late tenth appended, keys that belong in the top fifth of the file but arrive at its end in random order, the floor is 0.20 moves a key. The sort, with a buffer of a 64th of the file and the trim the skip the split already made gave it, moves 2.93. Two thirds of that is the late tenth sorting itself: a dozen levels of merging over 6,554 keys that arrived together and in no order.

That essay’s closing section proposed handling a short final stretch differently. The keys arrive together at the end, and at a 64th the buffer holds 1,024 of them. Take the tail a buffer at a time. Insert each key into a sorted piece kept in the buffer, then merge the buffered piece into the head, the long sorted run in front of it, and do the same with the next buffer’s worth. The prediction was that insertion into the buffer costs about half a buffer’s length in moves a key, far more than the dozen levels of merging at a 64th, so the rule pays only when the buffer is small. There, the late tenth should fall from 2.93 moves a key to under two. It named the failure: six pieces of a thousand keys, merged into the head one at a time, each cross the head’s top fifth, and six such crossings may cost more than the tail’s own sort saved.

The rule, and a second way of sorting a piece #

The sort finds the head with one pass, the longest sorted prefix. That pass is the one a run is a property of the input argued every adaptive sort should make, since the runs it finds are the input’s own measure of how sorted it already is. Here it finds one run of 58,982 keys and then a tail of 6,554 in no order, and the rule applies only to an input of that shape: a long head and a final stretch no longer than a tenth of the file. The tail behind it is taken in pieces of the buffer’s length. Every piece’s keys are written into the buffer, sorted there, and merged into the head from the right: the merge compares the largest key of the head with the largest of the piece and writes the larger to the free end, so every head key larger than the piece’s smallest moves up once, and every piece key is written once. The head then includes the piece, and the next piece follows.

Two ways of sorting a piece are measured. By insertion, as proposed: each key is placed in the sorted piece by binary search, and every key after its place shifts one step. By merging: the piece is sorted where it lies by the same buffered merge sort that sorts the whole file, then copied into the buffer. The second was not in the proposal. It was added once the first was measured, to separate what insertion costs from what taking the tail in pieces costs.

Moves are counted as the merge sort counts them, one for every key written, and every result is checked sorted. The keys are distinct, so stability is not at issue.

Insertion never comes close #

At a buffer of a 64th, sorting the late tenth a buffer at a time by insertion costs 25.96 moves a key of the file, nine times the merge sort’s 2.93; at its best, at a 256th, it costs 10.40 against 4.39. It never comes within twice the merge sort at any buffer measured. The proposal expected insertion to lose at large buffers and win at small ones. It loses at large buffers by the margin expected and at small ones by more, because at small buffers the pieces’ merges into the head grow faster than insertion’s cost falls.

The same pieces sorted by merging cost 2.41 moves a key at a 64th, 18% under the merge sort, and 1.91 at a 16th, 6% under. Below a 64th they lose, and at a 1,024th they cost 16.0, two and a half times the merge sort. At a quarter of the file the tail is one piece and the rule is the merge sort exactly, 1.89 both ways. The proposal’s target of under two moves a key is met only at a 16th and above, where the merge sort was already at 2.04; at the 64th it was aimed at, the best the pieces reach is 2.41.

So the proposal’s question has two answers. Insertion is the wrong way to sort a piece at any buffer measured. Taking the tail in pieces that fit the buffer is right at a 64th and a 16th, and wrong below.

A quarter of a piece, every key #

Inserting a tail key into a sorted piece costs a quarter of the piece’s length in moves, 248 for pieces of 1,024, not the half the proposal expected. The prediction counted a key shifting half of a full piece. A piece fills from empty, so on average it is half full when a key arrives, and a key lands on average in its middle and shifts half of what is there. A quarter is half of a half.

The comparisons are not the problem. Binary insertion finds each key’s place in about ten comparisons for a piece of 1,024, fewer than a merge sort spends on the same key. Every cost here is a write, and the count is of writes because a buffer-limited sort is a sort that is short of room to write into, which is the reason this line of pages counts moves rather than time, the choice counting instead of timing made for the whole collection.

The difference between a quarter and a half is a factor of two, and it does not change the verdict. At a 64th, a quarter of 1,024 is 256 moves for each of 6,554 keys, 24.8 moves a key of the file before any piece reaches the head. The merge sort’s whole cost is 2.93. Insertion’s cost per key grows with the piece and a merge level’s does not, which is the old trade where insertion sort actually wins priced for small arrays, and at a thousand keys it is a long way past its crossing.

Crossing the head, once a piece #

Every piece’s merge into the head moves the head’s keys above the piece’s smallest key, and on the late tenth that is most of the head’s top fifth every time: seven pieces of 1,024 cost the head 1.13 moves a key of the file, and 410 pieces of 16 cost it 58. The proposal named this failure and worried about six crossings. Six are affordable. Halving the piece doubles the crossings, and the cost into the head doubles with them.

The arithmetic is simple. The late tenth is drawn from the top fifth of the keys, so the head holds about a tenth of the file in that range, 6,550 keys. A piece of random keys from the range has its smallest key near the bottom of it, so nearly all of those head keys move on every piece, and so do the pieces already merged above them. One crossing is worth about 0.15 moves a key of the file, and $P$ pieces cost about $0.15P$.

Insertion’s cost into the buffer falls as the pieces shrink, a quarter of a piece a key, and the head’s cost rises. The two lines cross between pieces of 128 and 256, and their sum never falls below 10.40 moves a key. There is no piece length at which insertion pays.

Sorting each piece by merging costs between 0.46 and 1.29 moves a key into the buffer at every piece length, the merge sort’s own cost on a small array plus the copy. It is cheap at every length. What decides the rule’s total is the head, and the head wants few pieces.

What a piece that fits the buffer saves #

At a 64th the merge sort spends 1.04 moves a key rotating, and seven pieces that each fit the buffer rotate nothing; they spend 1.13 crossing the head instead, and come out 0.52 moves a key ahead. That is where the rule’s gain comes from, and it is not the gain the proposal described.

The merge sort sorts the whole tail first, 6,554 keys in a dozen levels, and then merges the sorted tail with the head. At a 64th that last merge cannot fit: its shorter run, the tail, is six times the buffer. So the library’s merge splits it by binary search and rotation until the pieces fit, the mechanism the buffer a schedule cannot bend traced, and the rotations move each key several times. The pieces never need that. Each one is the buffer’s length, so its merge with the head is a plain buffered merge, one write a key.

The proposal expected the rule to win by replacing the tail’s own sort with merges into the head. It does not replace the tail’s sort: the pieces sorted by merging still cost 1.29 moves a key, against the merge sort’s 1.89 for extending runs and for all of its buffered merging, the final merge with the head included. What it replaces is the rotation. At a 16th the tail is only one and a half buffers long, the merge sort’s rotation costs 0.15, and the rule saves only 0.13.

How far down the tail reaches #

The pieces pay while the tail belongs near the top: 0.25 moves a key saved when it is drawn from the top tenth, 0.52 from the top fifth, two hundredths from the top two fifths, and they cost 1.48 more when it is drawn from the whole file. Both of the costs being traded grow with the reach. The merge sort’s rotation grows because the final merge is spread over more of the head; the pieces’ crossings grow because each crossing moves more of the head. The crossings grow faster, seven of them against one rotation. From a tail drawn from the top tenth to one drawn from the whole file, the merge sort’s rotation grows thirteenfold, from 0.29 moves a key to 3.85, and the pieces’ crossings grow sixteenfold, from 0.43 to 6.72. A rotation’s cost is set by how far the final merge’s split points move keys, and a crossing’s by how many head keys lie above a piece’s smallest key, which on a tail reaching the whole file is nearly all of them, seven times over.

The two lines cross at about two fifths. Below that, a tail that fits seven buffers is better merged in seven pieces; above it, the whole tail is better sorted first and merged once, rotations and all. The crossing depends on the number of pieces as well as the reach, which is the subject of the closing section.

A tail that belongs anywhere #

When the appended tenth belongs anywhere in the file, the pieces lose at every buffer smaller than the tail: 3.51 moves a key against 3.24 at a 16th, 8.01 against 6.54 at a 64th. Every piece’s smallest key is near the bottom of the file, so every crossing moves nearly the whole head, and seven crossings of the whole file cost more than one merge with rotation. Insertion loses here by a factor of three at its best buffer and sixty at its worst.

This is the random tenth the earlier pages appended beside the late one, the input a request that reads the input first sized its buffer against. The late tenth was easier for the pieces because it belongs in one fifth of the file. The pieces are a way of exploiting exactly that confinement, and where there is none, they have nothing to exploit.

What the counts depend on #

One file, one draw. Each input is one permutation of 65,536 keys, and every number is a count on it. The late tenth’s keys are drawn once from the top fifth, so the piece boundaries fall at the same keys in every design, and the comparisons between designs are exact on this file. The moves are exact counts, so there is no sampling error in them, but another draw of the late tenth would move them a little.

A merge from the right, counted as the library counts. The pieces’ merges into the head write each moved head key and each piece key once. They do not use galloping, which the skip the split already made added to the merge sort’s merges as the trim. A head key below the piece’s smallest key is never touched either way.

The floor is unchanged. The least any sort with one spare cell can move on the late tenth is 0.20 moves a key, the floor the earlier essay computed from the permutation’s displaced keys and its twelve cycles. It is a floor on writes, as the floor a merge cannot reach was a floor on comparisons, and neither design comes near it. The pieces at a 64th move twelve times that, against the merge sort’s fifteen. Most of the distance to the floor is still the tail’s own sort, which neither design avoids.

Still open: how many pieces the head can afford #

The pieces won at a 64th by fitting the buffer and lost at smaller buffers by crossing the head too often. Those are two ends of one choice. A sort could merge pieces with each other before merging them into the head: two pieces of a buffer each merge into one of two buffers, which no longer fits, but four pieces merged pairwise and then the pairs into the head cross the head half as often as four pieces would, and pay one more level of merging inside the tail for it.

The cost of a crossing is known before it is made. The pass that finds the head ends at the tail’s first key, and a binary search for the tail’s smallest key in the head says how many head keys every crossing will move. A level of merging inside the tail costs about two moves a tail key; a crossing costs about the number of head keys above the tail’s smallest. The measurement that follows merges the tail’s pieces among themselves until one more level would cost more than the crossings it removes, then merges what is left into the head, and runs it at every buffer and every reach. On the late tenth a crossing moves about ten thousand keys and a level of merging the tail about thirteen thousand, so the rule should merge whenever there are more than three or four pieces. The prediction is that at a 64th it merges the seven pieces once, to four, and saves a little more than the 0.52 a key the pieces save now, and that at a 1,024th it merges the 103 pieces down to four or eight and comes within 20% of the merge sort. It could fail on the rotation it was designed to avoid: merged pieces are larger than the buffer, and their merges into the head rotate again. The question is whether a sort that knows what a crossing costs can always choose between crossing and merging well enough to beat sorting the whole tail first, or whether below some buffer the rotation is the cheapest way across.