A floor the ranks do not move

The wins two sources leave merged two sorted lists of repeated values drawn from sources that disagree — the same values with the same weights, but a value common in one list rare in the other — and found that one bar shared by runs of ties and runs of wins saves up to a third of the comparisons the bar for ties alone spends. It also found where the third came from: the tie bar collapsing toward the walk when ties stop being long, while the shared bar stays near where the tie bar had been on lists that agreed.

That left a question about principle the plates could not answer. The strand began from floors — the floor a merge cannot reach solved the game of merging two short lists of distinct keys exactly, and the merge that can say equal found the floor falling when the keys repeat — but no essay since had set a floor under the long lists the bars were measured on. The closing proposal was to compute it for disagreeing lists and place the merges against it. The prediction was that independent ranks lower the floor further than they lower the shared bar’s cost, so that the shared bar sits about a third above the floor where the tie bar sat a sixth above it on agreeing lists, and that the gap lies in the rare values’ short stretches, which a bar of seven never gallops. It named the way it could fail: the number of ways to interleave two lists that disagree might not fall at all.

Which floor can be computed #

An exact floor for one pair of lists of 1,024 keys is out of reach; the games that set the short-list floors were solved over every input of four or five keys. What can be computed is the floor of a class the pair belongs to, and the choice of class is the whole of the method.

Read the merged order as a sequence of labels, one for each key: which list it came from. A stretch is a maximal run of one label. Where both lists hold a value, its two runs can leave in either order, and the sequence takes whichever order continues the stretch already open, so that the stretch count is as small as the input allows. Call the counts $k_A$ and $k_B$.

Now consider every pair of sorted lists, of the same lengths, whose merged labels have exactly those stretch counts and which share no value at all. Each such pair has exactly one correct output, and different label sequences are different outputs, so a merge must be able to tell them all apart. There are $\binom{m-1}{k_A-1}\binom{n-1}{k_B-1}$ label sequences of that shape for each list that may start, and on inputs with no value in common a three-way comparison never answers “equal” — so on that class a merge is a binary tree, and counting gives its worst case:

$$\text{floor} = \log_2\binom{m-1}{k_A-1} + \log_2\binom{n-1}{k_B-1} + 1 \text{ comparisons.}$$

It is a floor over the class, not a bound on the pair in hand. A pair with ties is a cheaper input than the class’s worst, and a merge that hears “equal” can go under the floor on it. Where one does, that is not an error in the count; it is the third answer being worth something, and it is measured.

The count is checked on a small case: twelve keys in two lists of six, summed over every possible pair of stretch counts, give back the $\binom{12}{6} = 924$ interleavings of distinct keys exactly.

The floor on lists that disagree #

The floor rises with the number of values, from 0.060 comparisons a key at 16 values to 0.439 at 256 and 0.710 at 2,048, because more values mean more stretches and each stretch is a decision about where a list’s turn ends. Every merge sits above it at every number of values: the shared bar at 3.32 times the floor at 16 values, 1.37 at 256 and 1.09 at 2,048; the bar for ties alone at 1.91 at 256, and 1.34 even at 2,048, where its cost has nearly met the walk’s.

So on disagreeing lists the prediction’s ratio holds: the shared bar is about a third above the floor at 256 values. Under Zipf 1.5 it is closer — 1.20 at 256 values, 1.08 at 1,024 — and the bar for ties alone is three times the floor there, because steep disagreeing lists have very long stretches of wins that the tie bar walks one key at a time.

The floor on lists that agree #

On agreeing lists the floor is the same curve — that is the next section’s subject — and the merges are lower. At 256 values the bar for ties is 1.16 times the floor, the sixth the proposal recalled. At 512 values it reaches the floor, 1.01, and from 1,024 values it is under it: 0.93 at 1,024, 0.90 at 2,048.

That is the case the floor’s definition warned of. At 1,024 values on agreeing lists 79% of the keys share their value with a key of the other list, and every such value is a pair of runs that one “equal” answer places together. The class floor counts those pairs as two stretches that must be separated by binary answers, because on the class’s inputs nothing is ever equal. A merge on these inputs is not in that class and does better than its worst. The floor when the values repeat read merge sort going under $\log_2 n!$ the same way — a sign that the floor in hand is the floor of a different question.

On disagreeing lists nothing goes under the floor at any number of values under either skew; the nearest is a bar for each kind of stretch at 1.07 times the floor, under Zipf 1.5 at 2,048 values. With independent ranks only 32% of keys share a value at 1,024 values and 8% at 2,048 under Zipf 1.5, so the inputs are close to the class the floor describes, and the floor is close to theirs.

What independent ranks change, and what they do not #

At 256 values under Zipf 1, making the second list’s ranks independent of the first’s moves the floor by less than a thousandth of a comparison a key: 0.440 agreeing, 0.439 independent. Across every number of values and both skews the largest movement is five thousandths. The prediction’s mechanism — a floor falling faster than the merge — is refused outright: the floor does not fall.

It does not fall because it counts stretches, and the stretches do not change. Two lists drawn from the same weights over the same values hold about the same number of distinct values each, whichever values those are. On agreeing lists most values are in both lists, and the merged order is a chain of tied pairs — this value’s run from the first list, then from the second, then the next value’s run from the second and the first — which switches lists once a value. On disagreeing lists fewer values are shared, and the order is stretches of values only one list holds — which also switches lists about once a value. At 256 values both orders have 0.093 stretches a key; at 1,024, 0.167 and 0.168.

Every merge rises instead. The walk goes from 0.602 comparisons a key to 0.864, because without ties it can no longer place two keys for one comparison. The gallop on every tie goes from 0.679 to 0.785, the bar for ties from 0.510 to 0.838, the shared bar from 0.508 to 0.603, a bar for each kind from 0.512 to 0.593. Disagreeing sources make merging dearer for every merge and no cheaper in principle. The shared bar’s third, read against the floor, is not a share of a new saving that disagreement made available; it is most of what disagreement took away, recovered by galloping wins as the tie bar galloped ties. The shared bar on disagreeing lists is 0.16 comparisons a key above the floor; the tie bar on agreeing lists was 0.07 above it.

So the earlier essay’s question — whether disagreeing sources make a merge cheaper in principle or only cheaper for a merge that can gallop — has an answer neither half of it anticipated. They make it cheaper for nobody. The gallop over wins is how a merge pays back part of what they cost.

Over the floor, by values #

Each case’s natural merge — the bar for ties where ties are the long stretches, the shared bar where wins are — comes closer to the floor as the values grow, and on the same curve shape under both skews. At few values both are three or more times the floor; at 2,048 values the shared bar is within a tenth of it on disagreeing lists and the tie bar under it on agreeing ones.

The ratio is large at few values for a reason the next plate makes exact. At 16 values the floor is 0.06 comparisons a key, because there are few stretches and each is long, and the information in a stretch is the logarithm of where it might end. A merge that must first walk seven equal answers before it starts to gallop pays those seven on every stretch whatever its length, and when the floor allows only a few comparisons a stretch, seven is most of the cost.

The price of entering a stretch #

Divided by the number of stretches, the gap stops being a ratio and becomes a count. At 16 values a stretch averages 120 keys; the floor allows 7.25 bits to find where it ends, a doubling search with no bar in front of it pays 13.0 comparisons — the factor of two every doubling search pays over a binary search that knows its range — and the shared bar pays 24.0, eleven more than the doubling search: the bar of seven walked comparisons before the gallop starts, and the comparisons that confirm a stretch is still going.

At 1,024 values a stretch averages six keys; the floor allows 3.84 bits, a doubling search pays 3.79 and the shared bar 4.26. On short stretches the floor and the doubling search meet, and the bar’s walked entry is no longer an extra, because a stretch of six is mostly over by the time a bar of seven would have been reached.

That places the gap, and not where the proposal put it. Stretches of one or two keys hold 3% of keys at 256 values and 11% at 1,024; the rare values’ short stretches are a small part of the order and the merges handle them at the floor’s own rate. The gap is in the long stretches, and it has two parts: the doubling search’s factor of two, which no merge that does not know a stretch’s length can avoid, and the bar’s walked entry, which is the bar’s design — the price of not galloping a stretch that turns out short.

The uniform control #

The earlier essay’s control was uniform values, where every rank has the same weight and re-dealing ranks cannot change which values are common. It is a control here too, and it shows the floor and the ties from a third side.

On uniform values the floor is the same with ranks agreeing or not to a thousandth — 0.531 and 0.532 comparisons a key at 256 values — and so is every merge, 0.646 and 0.645 for the shared bar. Nothing distinguishes the two cases, as nothing should.

What the uniform lists add is a steeper floor. At 1,024 values a list of 1,024 keys drawn uniformly holds about 650 distinct values, and the merged order has 0.31 stretches a key, against 0.17 under Zipf 1, where a few common values gather most of the keys into long runs. So the floor at 1,024 values is 0.891 comparisons a key on uniform lists and 0.645 under Zipf 1: a skewed source is cheaper to merge in principle because its order switches lists less often, and that is the skew’s whole contribution to the floor.

And the uniform lists go under the floor earlier than the skewed ones, from 512 values, and further: the walk costs 0.761 at 1,024 values against the floor’s 0.891, 0.85 of it. Uniform lists over many values are the input where a value is most often held once by each list — 63% of keys share a value at 1,024 values — so a single “equal” answer places one key of each list together far more often than on skewed lists, whose shared values come in long runs. The walk itself is the merge that gains: it does nothing but compare heads, and on these lists a large share of its comparisons answer “equal” and place two keys at once.

A floor’s class is a statement about the question #

The essay found a floor that two different kinds of input share, and the sharing is the result. A merge’s cost on these lists is governed by two things the input offers, how often the merged order switches lists and how many of the switches come with an equal answer that places two runs at once. The floor counts the first and, by its construction, none of the second; agreeing and disagreeing lists have the same amount of the first and very different amounts of the second.

The floor moves when the question does made the general point that a floor is a count of answers, and the answers depend on what is asked. Here the class floor answers a merge that is never told “equal”, and on disagreeing lists that is nearly the merge in hand — which is why the shared bar comes within a tenth of it at many values and never under. On agreeing lists the merge in hand is told “equal” most of the time and the class floor answers a harder question than it is being asked.

A merge that decides per run and a bar that wins rarely meet treated the bar as a threshold to tune; the per-stretch plate prices it against the floor instead. At few values the walked entry costs eleven comparisons a stretch above a plain doubling search, which is a statement about how much the bar’s caution costs on inputs where every stretch is long — and when galloping pays gave the other side, the inputs where a gallop started too soon costs more than it saves.

What the floor does not cover #

A class floor, not an instance floor. The bound holds for the worst input of the class each pair belongs to. A floor for each pair — the fewest comparisons any merge needs on that pair and pairs like it in some finer sense — would need a different class, and on agreeing lists it must be lower than this one, since merges go under this one.

The ties’ value left unpriced. The floor says nothing about how much an equal answer is worth. The plates show it is worth enough to take merges 10% under the class floor at 2,048 agreeing values; a floor for a three-answer merge on inputs with a given number of shared values was not computed.

One length, the earlier lists. Every pair is two lists of 1,024 keys drawn as the earlier essay drew them, at full agreement or none. The half-agreeing lists, and other lengths, were not set against the floor.

Still open: a floor that knows the ties #

The class floor fails exactly where ties are common, and that failure has a shape that suggests the repair. A tied value is two runs that one comparison can place together, and an input with $t$ tied values among its stretches belongs to a smaller class than an input with none: its merged order is determined by the stretches between tied pairs, with every tied pair a stretch boundary the merge may learn with a single “equal”.

The measurement that follows counts that class — inputs with the same stretch counts and the same number of tied values, where a tied value is a pair of runs that may leave in either order — and takes the logarithm in base three where a comparison can answer three ways. The prediction is that this floor stays under every merge on agreeing lists, sits about a fifth under the bar for ties at 1,024 values and 2,048, and on disagreeing lists coincides with the class floor here to a hundredth, since there ties are rare. It could fail by being too low to say anything: a base-three count credits every comparison with an equal answer it seldom gets, and a floor that halves the bits a stretch on lists where nine keys in ten never tie would be true and useless. The question is whether the third answer can be priced from how often it is given, or whether a floor for merges that can say equal must be solved, not counted.