A floor that knows the ties
The strand that measured merges of sorted lists with repeated values began from floors. How close anything gets to the floor had measured sorts against the counting floor, and the floor when the values repeat found that floor falling when keys repeat. The floor a merge cannot reach solved the game of merging two short lists of distinct keys exactly; the merge that can say equal found that floor falling when keys repeat, because a three-way comparison that answers “equal” places two keys at once. For long lists no game can be solved, and a floor the ranks do not move set a floor by counting instead: read the merged order as a sequence of labels, A or B, one a key; count its stretches — maximal runs of one label — and ; and count every pair of lists with those stretch counts that share no value. A merge must tell them all apart, and on such inputs no comparison ever answers “equal”, so the merge is a binary tree and its worst case on the class is at least comparisons.
That floor held where it was built for. On lists whose ranks disagree — the same values and weights, but common in one list where rare in the other — no merge went under it at any number of values. On lists whose ranks agree, merges went under it from 1,024 values, by up to a tenth. The reason was in its own class: the inputs it counted share no value, and the real inputs share many. A merge that hears “equal” across two runs of the same value learns both at once, and the class floor had credited no comparison with that answer.
Its closing section proposed the class that keeps the ties. A tied value is a value both lists hold; its two runs sit at a boundary between stretches and may leave in either order. Count the inputs with the same stretch counts and the same number of tied values, and take the logarithm in base three, since a comparison can answer three ways. The predictions: the floor stays under every merge on agreeing lists; it sits about a fifth under the bar for ties at 1,024 values and 2,048; and on disagreeing lists it coincides with the old floor to a hundredth, since there ties are rare. The named risk: base three credits every comparison with an “equal” it seldom gets, and a floor that does so could be true and useless.
The class that keeps its ties
A merge here reports two things, and the class has to count both. One is the merged order as a label sequence; the other is which stretch boundaries are ties, because the merges in this strand join the two runs of a tied value and so report it. With and stretches there are label sequences for each list that may start, and among the boundaries any may be the ties: answers, each needing its own leaf. A tree in which every comparison has three answers needs depth at least to have that many leaves. That is the proposal’s floor, and it binds every merge on its class’s worst input.
A second floor prices the third answer instead of granting it everywhere. A tree whose paths hold at most answers of “equal” has at most leaves at depth , and on an input with tied values a merge that hears “equal” once for each needs only ; the least that reaches is a floor for such merges. Whether the merges here are such merges is a question with an answer, and the plates answer it.
Everything else is the earlier essays’. Two lists of 1,024 keys drawn from values under Zipf 1 and 1.5, each list sorted, with the two lists’ ranks agreeing or independent; five merges — the walk, the gallop, the bar for ties of a bar that wins rarely meet, the one bar for ties and wins of the wins two sources leave, and the split form of that bar — and the best of them at each setting; 32 trials a point; everything in comparisons a key.
The hero plate is agreeing lists at Zipf 1. The old floor crosses the best merge at 1,024 values, 0.645 comparisons a key against 0.597. The class counted with its ties, in base three, falls to 0.510 at 1,024 values and 0.569 at 2,048 — 15% and 11% under the bar for ties, against the fifth predicted — and stays under every merge at every number of values. The floor priced at one “equal” a tie sits at 0.555 and 0.635, the second within 1% of the best merge.
The same class at Zipf one and a half
At Zipf 1.5 the old floor again sits over the best merge from 1,024 values, 0.321 against 0.311, and the tie class in base three falls to 0.239 and 0.247 at 1,024 and 2,048 values — 24% and 21% under the bar for ties, about the fifth predicted. The steeper stream has fewer distinct values in use and longer runs of each, so the merges are cheaper, about a third of a comparison a key, and the floors fall with them. The base-three floor holds under every merge here too.
The priced floor is looser at this skew: 0.276 and 0.288 against the best merge’s 0.311 and 0.313, eleven and eight per cent under. Ties are rarer relative to stretches at Zipf 1.5 — 0.029 tied values a key against 0.06 stretches — so the priced floor’s allowance of one “equal” a tie is a smaller share of its comparisons, and it gains less on the base-three floor than at Zipf 1.
Read beside the hero plate, the two skews say the prediction about the bar for ties was right in size and loose in detail: a fifth at the steeper stream, an eighth to a seventh at Zipf 1. And the risk the proposal named did not arrive on agreeing lists: base three is not too low to say anything. From 256 values up the best merge is never more than 1.59 times it at either skew, and at 2,048 values at Zipf 1 it is 1.12 times.
On lists that disagree
On lists with independent ranks the base-three floor does not coincide with the old floor as predicted: at 1,024 values it is 0.504 against 0.647, 22% lower, because a third of the stretch boundaries there are still ties and base three discounts every comparison, tie or not. The prediction rested on ties being rare on disagreeing lists, and they are not. A value both lists hold is still a tied value when it is rare in one list and common in the other; what disagreement removes is the long matched runs that make ties valuable to a merge, not the ties themselves. At 1,024 values 33% of the boundaries are ties, at 2,048 values 20%.
And base three is a discount on every comparison, not on the ties alone. Dividing the class’s bits by treats each comparison as carrying 1.585 bits where a two-way comparison carries one; on lists where the old floor was already right — no merge went under it — the base-three floor gives away more than a fifth of it. That is the proposal’s risk, arriving not where it was looked for but where the old floor had been sound.
The priced floor gives away less: 0.590 at 1,024 values, 9% under the old floor, and 0.676 at 2,048, 5% under. Of the three, the old floor remains the highest valid statement on these lists, since no merge goes under it there; the class with ties is a weaker statement about the same inputs, because it counts them with more freedom than the merges actually use.
How often the merges hear “equal”
The third answer is heard more often than the ties it reports: at 1,024 values the bar for ties hears “equal” 2.2 times for every tied value when the ranks agree and 1.2 times when they are independent, because it walks a tied pair of runs key by key before it gallops — so the floor priced at one “equal” a tie does not bind it. The priced floor’s premise is a statement about merges, and these merges break it. The bar for ties compares the heads of two equal runs, hears “equal”, advances both, and does that up to its bar of consecutive equal answers before it gallops to the runs’ ends; the walk never gallops and hears “equal” at every step through every tied pair, 0.335 times a key.
So the priced floor’s closeness to the best merge at 2,048 values — 0.635 against 0.638 — is not a result about these merges. It says what a merge that learned each tie from a single “equal” would at least have to spend, and none of the five merges is one. That none goes under it is measured, not proved.
The plate’s right side says when the premise nearly holds. On lists with independent ranks at 2,048 values the bar hears 0.044 equal answers a key for 0.039 tied values, 1.1 a tie: ties are short there, a key or two each side, and the bar’s walk through them ends at once. Where ties are short, a merge hears each about once, and the priced floor is close to binding.
The best merge against each floor
The best merge as a multiple of each floor: the class that ignores ties falls under one on agreeing lists, 0.926 at 1,024 values and 0.898 at 2,048, base three stays at 1.12 or more, and the floor priced at one “equal” a tie comes to 1.006 at 2,048 values — the tightest statement the counts make, about a premise the merges do not keep. The plate sorts the three floors by what they can be trusted to say. The old floor is valid on independent lists and invalid on agreeing ones. Base three is valid on both, at a margin that narrows from three times at 64 values to an eighth at 2,048. The priced floor is valid for a kind of merge that is not on the plate.
The approach to one with more values is common to all of them and has the same reason. At few values the keys are long runs of a handful of values and every merge gallops through them in a few comparisons a stretch, far above what the counts, which charge a stretch only the information in its length, can see. At many values stretches are short and the floor’s account of them — where they begin, how many there are — is most of what a merge must learn. The floors are informative where merges work hardest.
On independent lists base three at 2,048 values sits 1.44 times under the best merge, and the old floor 1.09 times. The old floor is the one to use there; the new class does not improve it.
What a comparison is allowed to carry
Base three credits every comparison with log₂ 3 = 1.585 bits; a tree that hears “equal” once a tie still carries 1.459 bits a comparison at 1,024 values on agreeing lists, 92% of base three’s, because ties are 15% of the comparisons it makes; allowed as many "equal"s as the bar for ties hears, it carries 1.583, base three to two decimals. The proposal’s question was whether the third answer can be priced from how often it is given. The plate prices it both ways the measurement allows. Priced from how often the input can give it, once a tie, it is worth most of what base three credits, because on agreeing lists at many values ties are frequent relative to the comparisons a floor allows. Priced from how often the bar for ties actually hears it, it is worth all of it.
That is the plainest answer the strand has to the question the earlier floor left. A merge that hears “equal” as often as these do is, for counting purposes, a ternary tree, and base three is the right model of it; the gap between base three and the best merge, 12% at 2,048 values on agreeing lists, is then the merges’ room to improve or the counting’s slack, and the counting cannot say which. The priced floor shows that the slack could be smaller for a merge that asked fewer questions about its ties — but such a merge would have to find a tied run’s end without walking it, which is exactly what galloping does, and the bars gallop only after a walk; a merge that decides per run found when that walk pays for itself.
Which floor to quote
The three counts are not rivals so much as statements under different conditions, and the plates fix which to quote where. On lists whose ranks are independent, the class with no ties is the highest floor measured and no merge goes under it; it is the one to quote, and counting ties only weakens it, because the freedom the tie class grants — any boundary may be a tie — is freedom these inputs have and the merges barely use. On lists whose ranks agree, the class with no ties is false from 1,024 values, and the tie class in base three is the floor: valid on every input, within an eighth of the best merge at 2,048 values, and exactly the model the merges’ own habits justify, since they hear “equal” often enough to be ternary trees in every sense that matters to a count.
The priced floor is a different kind of statement: not a floor for the merges that exist but a target for one that does not, a merge that would hear each tie once. That it sits within 1% of the best merge at 2,048 values on agreeing lists says that the room left between base three and the merges is mostly the price of hearing ties more than once — not a failure of the counting, and not a property of the inputs. Whether a merge can collect that room is the question the next measurement takes up.
What the counting leaves out
A worst case over a class, not a cost on an input. Every floor here is the least depth of a tree that answers every input in its class; an input can be cheaper than its class’s worst, and on few values every merge is.
What a merge must report. The tie class counts an answer as a label sequence plus which boundaries tie; a merge that need not report ties has fewer answers to give, and a lower floor.
The priced floor’s premise. It binds merges that hear “equal” at most once a tie. None of the five measured is such a merge; that they stay above it is a measurement.
Still open: a merge that hears each tie once
The plates leave a specific target. The floor priced at one “equal” a tie is within 1% of the best merge at 2,048 values on agreeing lists, and every merge measured hears “equal” two or three times a tie, because the bars walk a tied pair of runs before they gallop. A merge built to the priced floor’s premise would, on its first “equal”, gallop at once — a doubling search for the end of each run — and so hear “equal” exactly once a tie, paying for the run’s length in two-way comparisons within each list instead of in three-way comparisons across them.
The measurement that follows adds that merge, galloping on the first “equal” with no bar, beside the five here, on the same lists, and counts its equal answers and its comparisons. The prediction is that it hears 1.0 “equal” a tie by construction, that it stays above the priced floor — so that floor binds it — and that on agreeing lists at 1,024 and 2,048 values it costs within 5% of the bar for ties, since the bar’s walk before galloping is short when its bar is low. It could fail on the short ties: a run of two equal keys galloped to its end costs three comparisons where walking it costs two, and on independent lists, where ties are short, the merge that gallops at once may be the dearest of the six. The question is whether a merge can be built to the floor’s premise without paying more than the premise saves.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- The runs a short list cannot have equal elements · galloping · information floor
The objects this essay names
Each one links to every other essay that touches it.
Counting argumentEqual elementsGallopingInformation floorMergingZipf distribution