The runs a short list cannot have

The merge that can say equal solved the game of merging two sorted lists when their keys take only a few values. With four keys a list over four values, only 27 different answers are needed, not 70, so the counting floor falls from seven comparisons to five. A merge whose comparisons answer only “at most” still needs seven on its worst input, because it can never learn that two keys are equal and so has to separate them as if they were distinct. A merge whose comparisons can answer “equal” needs five and meets the floor. On average, the third answer was worth more than solving the game.

That essay’s closing section noticed where the gain comes from and where it does not. The three-way merge gains whenever an equal answer places a pair of keys at once, and the gain grows with how many keys share a value, but it is taken only where one list’s head happens to meet an equal head in the other. A merge could look for runs of equal values deliberately: a comparison between two keys of the same list says whether they are equal, and a run found that way can be placed against the other list with one search rather than one comparison a key. It predicted that comparisons inside a list cannot help the worst case, since an adversary can make every neighbour distinct, and that on average with few values they should help a great deal, a run of $r$ equal keys costing about $\log_2 r$ comparisons to find and saving up to $r$. The question was where on $k$ the saving stops paying, the number of values below which a library should look for equal runs before merging.

The game, with comparisons inside a list #

The game is the earlier essay’s, which the floor a merge cannot reach first solved for distinct keys and found the counting floor short by a comparison at five keys a list. An input is a pair of sorted lists over at most $k$ values, up to the order of the values. A merge is a strategy of comparisons, and it is finished when one interleaving of the two lists is correct for every input still consistent with the answers. Solved by minimax over the sets of inputs still possible, it gives the exact fewest comparisons on the worst input and on average, the average over lists whose keys are drawn uniformly from the $k$ values.

The one change is a new kind of move. Besides comparing a key of one list with a key of the other, which answers less, equal or greater, a merge may compare two keys of the same list. The lists are sorted, so that answers “equal” or “less”, and “equal” says every key between the two is equal as well. Without the new move the solver reproduces the earlier essay’s three-way game exactly. With it the game has twelve more moves at four keys a list, and the state space grows quickly. At two values the solver visits 2,239 sets of inputs, at three 56,713, at four 230,605, over 24, 177 and 648 inputs; solving it at four values took about a hundred seconds, and five values was not attempted. The comparisons inside a list do not only add moves. Every one of them splits the inputs along a line no comparison across would draw, so the sets of inputs the solver meets are new sets, and there are many more of them.

Solved: nothing to find #

Solved exactly at four keys a list, comparisons inside a list leave the worst case where it was at every number of values, and move the best average by under seven thousandths of a comparison. The first half of the prediction holds, for the reason it gave: an adversary can make the keys of a list distinct, and a comparison that can only say “less” between two distinct keys of a sorted list says nothing the merge did not know. It is the adversary argument the adversary who hides the edge used where counting outputs gave a useless bound: the adversary answers each question in the way that keeps the most inputs alive, and a question whose every answer keeps all of them alive is a question wasted. The second half fails, and not by a little. With two values, where runs are longest, the best average does not move at all.

The reason is the size of a run in a list of four. With two values drawn uniformly, each list holds two keys of each value on average, and a run of two found by a comparison inside the list saves at most one comparison across. But a comparison across that answers “equal” already places two keys, one from each list, in one comparison. The three-way merge was already taking half a comparison a key on every equal pair. A comparison inside a list places one key, and so it can only beat a comparison across on a run long enough that finding its end is cheaper than walking it in equal pairs.

Why an equal answer is already half a gallop #

The arithmetic of the trade fits in a line. Two runs of $r$ keys of one value, one in each list, are walked by the three-way merge in $r$ comparisons across, each answering “equal” and placing two keys. A gallop finds the end of a run of $r$ in about $\log_2 r$ comparisons doubling outward and $\log_2 r$ more halving back, so the pair of runs costs about $4\log_2 r$ comparisons inside the lists and one across. The gallop wins when $4\log_2 r + 1 < r$: it loses at $r = 16$, where the two sides are 17 and 16, and wins at $r = 32$, 21 against 32.

That is the crossing every measurement below finds. It is also a different trade from the one the proposal priced. The proposal compared a gallop’s $\log_2 r$ with the $r$ comparisons a merge spends placing a run one key at a time. But the three-way merge never places an equal run one key at a time; it places it two keys at a time, one from each list, at half a comparison a key. Against that the gallop has to save twice as much, and it has two runs to find, not one.

The galloping merge on short lists #

At four keys a list the merge that gallops over runs loses at every number of values, 7.63 comparisons on average at two values against the textbook merge’s 4.00. The galloping merge is the textbook merge with one habit added. Whenever a comparison across answers “equal”, it finds how far that value’s run extends in each list by comparing the run’s first key with the keys one, two and four places on until one differs, then halving back, and it places both runs whole before comparing across again. That is the idea when galloping pays measured in Timsort’s merge, turned toward equal keys.

On a list of four the gallop always costs more than it saves. With one value, every key is equal, and the textbook merge needs four comparisons across, each placing a pair; the galloping merge needs one comparison across and three in each list to find that the runs reach the end. Galloping has a fixed cost of a few comparisons for each run it explores, and a run in a list of four is never long enough to repay it.

Long lists, where runs exist #

At 1,024 keys a list the galloping merge needs 0.019 comparisons a key with one value, a twenty-sixth of the textbook merge’s 0.500; it still wins at 32 values and loses from 64 on. With few values the runs are long, and finding a run of $r$ keys by galloping costs about twice $\log_2 r$ comparisons a list, while walking it in equal pairs costs $r$ comparisons across. The proposal’s arithmetic was right for long lists, and the saving is as large as it said.

This is the regime the floor moves when the question does described: with one value there is a single correct answer, so the floor is nothing, and a merge that asks whether the lists’ runs reach their ends can certify that answer in a logarithmic number of questions. The textbook merge keeps asking about pairs of keys long after the answer is settled.

With many values the gallop is a tax. Every equal pair the merge meets starts two searches, and when runs are a key or two long each search costs a comparison or two to find nothing. At 512 values the galloping merge makes 1.277 comparisons a key, two thirds again as many as the textbook merge, because it pays to explore runs that are almost never there.

The rule is a run length #

At every list length the galloping merge starts to pay at the same run length: when a value’s run averages between 16 and 32 keys a list. Drawn against the mean run, $m/k$, the four lengths’ curves fall on top of one another. The saving is a property of the runs, not of the lists: a merge that knew the mean run of its inputs would know whether to gallop, whatever their length.

That gives the proposal’s question its answer in a form a library can use. The number of values below which a merge should look for equal runs is about a thirty-second of the list’s length; stated without the length, a merge should gallop over equal runs when they average more than about thirty keys. A one-pass count of distinct values, or a sample of the runs, would tell it which side it is on.

The crossing grows with the lists #

The largest number of values at which galloping still pays is a thirty-second of the list’s length at every length measured: 2 at 64 keys, 8 at 256, 32 at 1,024 and 128 at 4,096. The thirty-two is not a magic number of this merge. It is where twice $\log_2 r$, the cost of galloping to the end of a run in each list and back, falls below the half-comparison a key the textbook merge already pays for a run walked in equal pairs, with the comparisons spent finding the runs’ ends and the occasional run of one counted in.

The pattern that defeats the pattern measured pdqsort noticing many equal keys while partitioning, and making a choice of the same kind: when a pivot equals the partition’s predecessor, it puts every equal key aside at once. Both rules turn on runs of equal keys long enough to be worth naming. This one says how long that is for a merge.

Where the galloping merge’s comparisons go #

With many values the galloping merge still saves comparisons across the lists, 0.565 a key against the textbook merge’s 0.760 at 1,024 values, and spends 0.675 inside them to do it. With few values almost all its comparisons are inside the lists, finding the ends of long runs, and the comparisons across fall to almost nothing. With many, every run it explores is a key or two long, so a search costs a comparison or two and saves at most one walk across. The crossing is where the comparisons inside stop costing less than the walking they replace.

This is the shape the floor when the values repeat priced from the other side: the floor for sorting keys from few values is far below $\log_2 n!$, because most of the orderings it counts are of keys nobody can tell apart. A merge that names runs reaches toward that lower floor; one that names keys one pair at a time cannot.

How far from the floor #

Neither merge on long lists is optimal, and nothing here says how far either is from the best possible. On the four-key lists where the game could be solved, the textbook three-way merge averaged 4.69 comparisons at four values against the solved optimum’s 4.19, about an eighth above it. How close anything gets to the floor measured sorts’ distances from the information floor in the same spirit; for merging repeated values on long lists the floor itself, the logarithm of the number of distinct correct interleavings, was not computed, and that is the comparison this essay cannot make.

What the counts depend on #

Solved only at four keys a list and four values. The game with comparisons inside a list was solved exactly where it could be; at larger sizes only the two merges were measured, and neither is optimal. The solved game says that at four keys a list nothing can be gained, which is a statement about short lists, not a bound on long ones.

Sampled, not exact, on long lists. Each point at 64 to 4,096 keys a list is the mean of 64 pairs of lists drawn with fixed seeds, so a crossing between two powers of two is located to within a factor of two.

One way to gallop. The galloping merge searches each list separately, outward from the run’s first key by doubling and back by halving. Searching one list for the end of the other’s run, or galloping from a guess set by the previous run’s length, would spend fewer comparisons on the long runs and the same on the short ones; neither was measured, and either would move the crossing toward shorter runs without removing it, since a run of one or two keys costs at least a comparison to rule out.

Uniform values. Every value is equally likely, so runs have about the same length. A skewed distribution would mix long runs of the common values with short runs of the rare ones, and a single run length would no longer decide; a merge would want to gallop on some values and not others.

Still open: a merge that decides per run whether to gallop #

The rule found here is a threshold on the mean run, and it is a rule about the whole input. A skewed input would want it value by value: gallop over the run of a common value and walk the run of a rare one. A merge cannot know a run’s length before it explores it, but it can know how the last few runs went, the way Timsort’s merge raises and lowers the bar for entering galloping mode according to whether galloping has been paying. That bar starts at seven consecutive wins and moves by one each time galloping pays or fails, and Timsort is the merge most programs call when they sort, as the sort the library ships found; it gallops on runs of one list beating the other, never on runs of equal keys, which its comparison cannot see.

The measurement that follows gives the galloping merge that adaptive bar: it gallops over an equal run only when the last few runs it explored averaged more than a threshold, and walks otherwise, and it runs on uniform inputs and on Zipf-distributed values at every list length. The prediction is that on uniform inputs it matches the better of the two merges within a few per cent on both sides of the crossing, and that on skewed inputs it beats both, galloping through the common values’ long runs and walking the rare ones’. It could fail at the boundary between them: on a skewed input the runs alternate between long and short in no order, and a bar set by the last few runs is always set by the wrong ones. The question is whether a merge can learn its inputs’ run lengths as it goes as cheaply as it learns them from a count in advance.