Every number of rounds, priced

The sort the library ships is a stable merge sort that finds the runs already in its input, and a run is a property of the input gave it a file that is sorted but for a late tenth: a long sorted head and a tail of keys that arrived out of order. The library merge sorts such a file with a buffer of a fixed size, and how many pieces the head can afford found the moves it makes depend on a choice the merge does not know it is making. It sorts the tail a buffer’s worth at a time into pieces, and then it can send every piece straight into the head, merge the pieces all the way into one group and cross the head once, or anything between: merge pairs into fours for some number of rounds, and send the groups that result. Trying every number of rounds, that essay found stopping partway was never the cheapest.

The rotation that could be priced and the head each piece will meet built a rule that chooses between the two ends before moving anything. Every price comes from a table measured once on synthetic inputs — the moves of one sorted run of $t$ keys crossing a head when it interleaves with the head’s top $A$ keys, and the moves of merging random pieces into one group — never from the file being sorted. Each piece’s $A$ is read by binary search: the head keys above its smallest key, plus the keys above it in every piece that will have joined the head before it. Priced that way, the pieces came within 6% of what they cost and the rule chose the cheaper end at all seven buffers and all ten reaches.

That essay’s closing section noted what it had left untested: the middle. It proposed pricing every number of rounds from the same two kinds of table — the rounds from a measured merge of random pieces to that many rounds, and each resulting group’s crossing at the count of keys it will meet — letting the rule choose the cheapest, and comparing with the measured cost of every number. The prediction was that the priced rule would never choose a partway number at any buffer, and that its estimate of every number would lie within 6% of its cost. It named the risk at buffers near the crossing between the two ends, a 128th and a 256th, where one round might cost the pieces less than it saves the head, and where the earlier essay’s single input might have hidden a partway optimum.

Priced at every number of rounds #

The file, its tail and the library merge are the earlier essays’: 65,536 keys, the last tenth arriving late and reaching a fifth of the way into the keys in the main runs, every move of a key counted, buffers of a 16th to a 4,096th of the file. After $L$ rounds of pairwise merging the pieces are groups of $2^L$ consecutive pieces, sorted. The price of $L$ rounds is the measured moves of merging that many random pieces of a buffer each for $L$ rounds, plus every group’s crossing from the table, each at the head keys above its smallest key plus the keys above it in every earlier group. Both are measured on synthetic keys from a separate generator; the file is read only for the binary searches that count its groups’ $A$. The measured cost of each $L$ is the library merge run with exactly that number of rounds.

The right choice at every buffer #

At a buffer of a 1,024th every number of rounds is priced within 4.1% of its measured cost except the first, which is priced at 21.76 moves a key against 18.97, 14.7% high; the rule chooses seven rounds, the cheapest measured, 6.46. The measured curve is the shape the earlier essays drew: one round dearer than none, because pairs of pieces are twice the buffer and cross the head by rotation rather than in the buffer; then every further round cheaper, as fewer and larger groups cross the head fewer times; and the minimum at the end. The priced curve follows it everywhere but the first round.

Across the seven buffers on this input the rule chooses the cheapest number of rounds every time: none at buffers of a 16th to a 128th, all at a 256th to a 4,096th. That much of the prediction holds exactly, and the choice is never partway because the measured cheapest is never partway on this input.

The first round’s price #

At buffers of a 16th to a 128th every estimate is within 5% of its cost, and at the three smallest buffers the first round is priced worst — off by −15.3%, +14.7% and −25.1% at a 256th, a 1,024th and a 4,096th, against at most 6.1% for any other number of rounds there. The second half of the prediction fails, and it fails at one place. The estimate of no rounds is within 6.1% everywhere, the estimate of all rounds within 1.6%, and every partway number from two up within 5%; the first round is the outlier, and its error changes sign between buffers.

The first round is where the table’s assumption is least true. The crossing table prices a run whose keys are spread at random over the head’s top $A$ keys. A group of two pieces after one round is a sorted run of twice the buffer, and at small buffers it is the first size that cannot be merged inside the buffer: it crosses the head by rotation, the move the earlier essays found the dearest and most variable. Its cost then depends on exactly where its keys fall among the head’s — which runs of its keys land together between two head keys — and a table measured on random spreads gives the average of a quantity whose value on this file’s groups is not average. With two rounds or more the groups are long enough that their keys’ arrangement among the head averages out, and the table is right again.

The rule survives the error because the first round is never close to the cheapest. At every buffer the measured cost of one round exceeds the cost of none by 5% to 19%, and an estimate 25% low at a 4,096th, 49.4 against a measured 65.9, is still far above the cheapest, all nine rounds at 8.87.

Across reaches #

Across five reaches and three buffers the priced rule chooses the cheapest number of rounds in 14 of 15 settings; the one partway optimum among them — at a 1,024th, the tail reaching a tenth into the keys — it misses by 3.8%, choosing five rounds where six were cheapest, and everywhere else the cheapest number is none or all. The risk the proposal named was the right kind and in the wrong place. It expected a partway optimum near the crossing between the ends, at a 128th or a 256th; the one found is at a 1,024th, far on the “all” side of the crossing, and at the shortest reach, where the tail’s keys all fall among the head’s top tenth.

The reaches move the crossing between the ends. At a reach of a tenth or a fifth a buffer of a 128th prefers none and a 256th none or all depending on the reach; from a reach of 0.4 every one of the three buffers prefers all rounds, because a tail spread over more of the head pays more for every piece that crosses it separately.

The partway optimum #

The one partway optimum found: with the late tail reaching a tenth into the keys, at a buffer of a 1,024th six rounds of seven cost 4.292 moves a key against all seven’s 4.332, and the priced rule, reading 4.479 for five rounds as cheapest, chooses five — 3.8% dearer than the best. The last round here merges two groups of 3,277 keys each into one of 6,554, and the whole tail reaches only a tenth into the head, so crossing the head as two groups costs almost exactly what crossing it as one does; the round itself costs more than the difference. That is the boundary the earlier essay had hoped did not exist: where the saving of one more round is smaller than its cost, the cheapest number is one short of all.

The miss is the pricing’s, not the rule’s. Its estimates for five rounds are right to half a per cent, 4.48 against 4.46, and for six and seven rounds 6.5% and 11.7% high, 4.57 and 4.84 — the last two rounds on this input are mispriced the way the first round is elsewhere, and in the same direction as the groups grow long against a head they barely reach into. The three measured costs lie within 4% of each other, and in a range that flat, a table wrong by a few per cent at its end ranks its entries wrongly. The regret is the size of the table’s error.

Why the end of the curve goes flat #

On the main input every further round after the first saves moves, and the saving shrinks as the rounds go on: at a 1,024th, the third round saves 3.95 moves a key, the fifth 1.48, the seventh 0.38. Each round halves the number of groups that cross the head, and a group’s crossing costs about the head keys it passes plus its own length, so the saving of a round is roughly the head keys that half the groups no longer pass — large while groups are many, small once they are few. Each round also costs its own merge, about two moves a tail key, a fifth of a move a key of the file when the tail is a tenth. The curve is cheapest at the end while the last round’s saving exceeds that.

At a reach of a tenth the head keys a group passes are few to begin with, because the late keys all belong in the head’s top tenth. The saving of every round is smaller by the same proportion, and by the last round it has fallen below the round’s own cost: six rounds leave two groups, and merging them into one costs 0.04 moves a key more than the crossing it saves. The partway optimum is where the two lines — a saving falling geometrically and a cost staying flat — cross before the rounds run out. Any file whose late keys reach only a little way into the head will have one, at small enough buffers, and the curve will be flat around it.

What pricing the middle costs #

Pricing every number of rounds reads more of the file than pricing the two ends. For each number of rounds the rule must form that round’s groups and count, for every group, the keys above its smallest key in every earlier group — one binary search of each earlier group, so that pricing $L$ rounds of $g$ groups costs about $g^2/2$ searches, and since the groups halve with every round, pricing every number costs about a third more than pricing no rounds alone, the largest term. At a 4,096th, with 410 pieces, that is about 112,000 binary searches of a few hundred keys each, against 84,000 for the no-rounds term alone. The ends rule paid the no-rounds term and one search for the single group, so the middle’s price is the third more, paid on every file whether or not its curve has a middle worth finding.

So pricing the middle costs the same order as pricing the ends, and on these inputs bought nothing: the ends rule’s one disagreement with the full rule, at the partway optimum, favoured the ends rule.

A sharp boundary, nearly #

The closing question was whether the boundary between the ends is sharp, or a narrow band of buffers where merging a little is cheapest and no rule of all or nothing can be right. On these inputs it is sharp: at fourteen of fifteen settings, and at all seven buffers on the main input, the cheapest number of rounds is none or all. The exception is not a band of buffers at all but a flat stretch at the far end of one curve, where the last round is worth almost nothing, and the cost of getting it wrong there is a few per cent.

That makes the rule of the earlier essay — price the two ends and take the cheaper — almost as good as pricing every number: it would have chosen all seven rounds in the partway case, 4.33 against the best 4.29, a regret of 0.9%, smaller than the full rule’s 3.8%. Pricing the middle bought nothing on these inputs and cost a little where the middle was flat. Pieces that fit the buffer and the moves no stable sort can skip both found that the library merge’s costs are dominated by a few structural thresholds — whether a run fits the buffer, whether a crossing must rotate — and the first round’s mispricing is one of them showing through a table built to average it away.

What the tables do not hold #

One file length. 65,536 keys, a late tenth. The number of possible rounds grows with the tail over the buffer, and a longer tail at a small buffer has more partway numbers, and more chances of a flat stretch at the end.

Random spreads. The crossing table assumes a run’s keys are spread at random over the head’s top keys. The late tail here is random within its reach, which suits the table; a tail whose keys clustered among the head’s would be mispriced at every number of rounds, not only the first.

Moves, not time. Every cost is moves of keys, the library merge’s own measure. Comparisons and the binary searches the rule makes are not charged, and the rule’s searches grow with the number of groups it prices.

A guarantee that depends on an allocation is the reminder that the buffer is the parameter every number here turns on, and the library chooses it from the memory it is given, not from the input.

Still open: a first round priced as pairs #

The rule’s one systematic error is the first round: its groups are pairs of pieces, the first runs too long for the buffer, and a table of single random runs prices their crossing 15% to 25% wrong. The calibration can be made of what the first round actually produces. A second table could be measured once, on synthetic inputs as before: two sorted pieces of a buffer each, merged by rotation into a run of twice the buffer, then crossing a head at each $A$, so that the first round’s groups are priced by the cost of exactly their kind of run.

The measurement that follows adds that table, prices the first round from it and every other round as now, and repeats every buffer and reach. The prediction is that the first round’s error falls under 6% at every buffer, and that the rule’s choices do not change, since the first round was never close to the cheapest; and that the partway miss at a 1,024th remains, since it is a flat stretch at the other end of the curve. It could fail if the first round’s mispricing is not about pairs but about where the file’s groups sit relative to the head, which a synthetic table cannot know. The question is whether a cost that depends on a run’s arrangement can be priced from synthetic runs of the same shape, or only from the run itself.