The merge that can say equal

The floor a merge cannot reach solved the game of merging two sorted lists of distinct keys. A merge of $m$ keys into $n$ must be able to give $\binom{m+n}{m}$ different answers, one for each way the lists can interleave, so counting says it needs at least $\lceil\log_2\binom{m+n}{m}\rceil$ comparisons. Solving the game exactly — every state of knowledge, every possible comparison, the adversary’s best reply — found that counting is right up to four keys a list and one comparison short from five: 252 outcomes say eight comparisons, and the game needs nine.

Every key there was distinct, and its closing section named that as the assumption most worth dropping. The floor when the values repeat had shown that repeated values lower the floor under sorting by more than half, because equal keys need no relative order. A merge of two lists drawn from a few values should have far fewer outcomes in the same way: a key of the first list equal to a key of the second may go on either side of it. The section predicted that the counting floor would be more wrong in the worst case with few values, not less. A comparison that comes out equal carries more information than either strict answer and is rarer, so it is exactly the kind of answer an adversary can decline to give. If that held, only merges that treat equality as a third outcome could approach the lower floor at all.

The game can be solved again with ties in it, and the answer divides along exactly the line the prediction drew. The division is sharper than predicted: whether the third answer exists matters more than anything else about the merge.

What an input is when keys can be equal #

With repeated values, an input is no longer an interleaving. It is two sorted lists read as a sequence of value classes, each holding some keys of the first list and some of the second. Two lists of four keys over at most four values can be arranged 648 ways. A merge’s answer is still an interleaving, and an interleaving is correct for an input when every key of the first list sits among the keys of the second at a place its value allows.

Where distinct keys give each key of the first list one correct position, equal keys give it a range. In the input drawn, a1 equals b1 and may go before or after it; a2 and a3 equal b4 and may go on either side. A merge is finished when it knows enough to choose a position inside every range at once, for every input still consistent with what it has asked. The condition has a short form. For each key, take the largest lower end and the smallest upper end of its range over the inputs still possible. The merge is done when the first is never above the second, and then placing each key at the largest lower end is a correct answer for all of them.

That condition turns the game into something that can be solved exactly. A state is the set of inputs still consistent, kept as a bitset over the 648. A comparison splits the set by its answer, and memoised minimax over the splits gives the exact optimum. It is exact on the worst input and on average over lists whose keys are drawn uniformly from the $k$ values. The merge is taken to know $k$, so the optimum found is a lower bound for any merge that does not.

Fewer answers than inputs #

The counting floor needs the number of different answers a merge must be able to give, and with ties that is not the number of inputs. Equal keys make one interleaving correct for many inputs, so the question is the fewest interleavings that cover every input, found by exact search. With four values, two lists of four have 648 inputs but 27 interleavings answer all of them, against 70 for distinct keys. The inputs grow with $k$ — there are more ways to arrange keys over more values — while the answers needed grow towards the distinct case, since with enough values ties become rare. The counting floor is the logarithm of the answers: three comparisons at two values, four at three, five at four, rising to seven with seven or eight values.

So the prediction’s first half is right before any game is solved. Repeated values lower the floor, and they lower it more than the number of inputs would suggest. The floor moves when the question does found that a floor is set by how many answers an algorithm must be able to give, not by how many inputs it might see, and ties are a case where the two part company.

The comparison that cannot say equal #

Two games are solved. In the two-way game a comparison of $a_i$ with $b_j$ answers “$a_i \le b_j$” or not. That is what < or <= in merge code returns, with a tie sent to one side, and what the standard library merges ask. In the three-way game it answers less, equal or greater, which is what a comparator returning a sign reports.

With four values the counting floor is five comparisons. A two-way merge needs seven on its worst input — exactly what distinct keys need — and a three-way merge needs five. From four values up, the two-way merge gains nothing in the worst case from the ties. At two and three values it does gain, since there are too few values for the adversary to build a hard input, but from $k = m$ on it is back at the distinct-key optimum. The three-way merge follows the floor down. It meets it at two, three, four, five, seven and eight values, and misses it by one at six.

The reason is in what “$a_i \le b_j$” can say. It is yes exactly when fewer than $j$ keys of the second list are strictly below $a_i$. So everything a two-way merge can ever learn is, for each key of the first list, how many keys of the second lie strictly below it — the lower end of its range — and nothing about the upper end. A tie widens a key’s range upwards, and a two-way merge cannot see that the range is wide.

Ties also let few values produce many patterns of lower ends. Distinct keys give 70 patterns for four keys a list, one for each interleaving. With ties allowed, four values produce 69 of them: the pattern of an alternating interleaving, for instance, comes from pairing a1 with b1, a2 with b2 and so on at four values. With ties forbidden, four values produce only 26. So a two-way merge over four values faces nearly the whole distinct-key problem, and needs the distinct-key worst case. Solved on inputs without ties, the same two-way game over four values needs five comparisons, not seven. The adversary uses the ties, and the two-way merge cannot tell it is doing so. That is the shape of the argument the adversary who hides the edge used for graph connectivity: the adversary keeps every answer consistent with an input the algorithm cannot rule out, and here the input it cannot rule out is one with ties it cannot see.

A three-way comparison reads both ends of a range. “Less” says $a_i$’s range ends before $b_j$, “greater” that it starts after, and “equal” that $b_j$ lies inside it. The prediction pictured the equal answer as the valuable one, which an adversary would decline to give. What the three-way merge gains is more general: every answer, equal or not, now says where a range can end, and a merge only has to find one position inside each range.

On average, the third answer beats the best strategy #

The textbook merge is the loop every library merge is built from: compare the heads, take the smaller, repeat. Its three-way form takes both heads when they compare equal and advances both lists. With keys drawn uniformly from four values, the two-way textbook merge makes 6.23 comparisons on average and the three-way one 4.69. The best two-way merge of all, solved exactly, makes 5.60. The textbook loop with the third answer is better on average than the optimal strategy without it at every $k$ from four to eight; at eight values it is 5.30 against 6.10. At three values the optimal two-way strategy is still ahead, 4.06 against 4.41.

The three-way textbook merge is no cleverer than the two-way one; it uses an answer the other throws away. Every equal comparison places two keys at once, and with four values and eight keys equal heads are common. The solved optimum adds what cleverness can add on top: from 4.69 to 4.20 at four values, about half a comparison, against the one and a half the third answer is worth on its own.

At two values the solved games coincide at 2.10 comparisons, against 5.75 and 4.00 for the two textbook merges. With two values an input is two boundaries, one in each list, and a merge that searches for them rather than walking the lists needs only three comparisons at worst. When galloping pays measured Timsort’s merge switching to that kind of search when one list keeps winning, and with two values that is the whole of the problem.

Why libraries ask the two-way question #

Every library merge measured in this collection asks the two-way question. The sort the library ships found Timsort in Python, Java, Rust and Android, introsort in C++, and dual-pivot quicksort for Java’s primitives. The interfaces they sort through all ask one thing of a pair of keys: whether the first is less than the second. C++'s std::merge takes a comparison that must be a strict weak ordering. Python’s sorted calls __lt__ and nothing else. Rust’s slice sort is written against is_less. None of them can be told that two keys are equal, because the question they ask has no such answer.

There are sound reasons for that. A strict weak ordering is the least a caller must supply, and it is enough for a sort to be correct. For distinct keys the two-way question loses nothing, and as ties become rare the solved games coincide in the worst case — from six values up at four keys a list. The cost falls on inputs with few values, and there it is the cost measured here: two comparisons in seven on the worst input at four keys a list and four values, and a quarter of the textbook merge’s average.

The three-way answer is usually available. A comparator that returns a sign computes it anyway, and one comparison of two integers or two strings costs the same whether the result is reported as a sign or as a boolean. So the saving is not bought with extra work per comparison. It is thrown away at the interface, by a function that computes three answers and reports two.

How far each game sits from the floor #

The counting floor is most wrong for the two-way merge with a few values, and least wrong with distinct keys: at four into four it misses by 0, 1, 2, 1, 1, 0 and 0 comparisons as $k$ runs from two to eight. The largest gap, two comparisons, is at $k = 4$. There the floor has fallen furthest relative to what the two-way merge can use. The three-way merge misses the floor only at four into four with six values, by one; at three into three it meets it at every $k$. The prediction said the floor would be more wrong in the worst case with few values, and for the merges that libraries ship, it is.

Five into five follows the same pattern where it can still be solved. With four values the floor is six comparisons, the three-way merge needs six, and the two-way merge needs eight, two above the floor and one below the nine that distinct keys need. At three values the floor is four and both games need five. That solve visits 428,199 sets of inputs in the three-way game, and five values take it past what an exact solve here can hold; that is where the table stops.

How close anything gets to the floor measured sorting algorithms against the counting floor and found merge sort within 2.2% of it. That was with distinct keys, where a merge’s two-way comparisons lose nothing. With repeated keys the same merge sort is measured against a floor it cannot see, because none of its comparisons ever reports a tie. The floor fell, and the algorithm’s cost did not.

What the solve does and does not cover #

Small lists, exactly. Every number is exact, over every input, for lists of three, four and five keys. Nothing here says how the gap grows at larger sizes. The distinct-key page found its gap growing as half the logarithm of the length, and the equal-key gap may grow differently.

A merge that knows $k$. The solved merges are told how many values there can be, which lets them stop as soon as the inputs still possible share an answer. A merge that does not know $k$ must assume the worst, so the optimum here is a lower bound for it. The textbook merges do not use $k$ at all, so their counts are what they are.

One question at a time, between the lists. Every comparison is between a key of one list and a key of the other, as in merging. Comparisons within a list tell a merge nothing it does not know from the lists being sorted, except whether neighbouring keys are equal. A three-way comparison of neighbours could reveal a run of equal values and is not in either game.

Uniform values, for the average. The averages draw each key uniformly from $k$ values. A skewed distribution makes ties among the common values more frequent and would widen the three-way advantage on average.

Ranges are what a merge may use; stability is what a library promises. A stable merge must put equal keys of the first list before those of the second. That removes the ranges, so a stable merge is solving the distinct-key problem whichever game it is in. The pattern that defeats the pattern found pdqsort handling a few distinct values with a partition scheme that groups equal keys, which is the same freedom used in a sort that makes no stability promise.

Still open: a merge that finds its runs of equal keys first #

The three-way merge gains because every equal answer places a pair of keys at once. 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 three-way comparison between neighbours in one list says whether they are equal, and a run of equal keys, once found, can be placed against the other list with one search rather than one comparison a key.

The measurement that follows adds comparisons within a list to the three-way game and solves it again at the same sizes. It asks whether the worst case falls below the between-lists floor, and what the textbook-plus-runs merge — gallop over a run of equals before comparing across — costs on average against the solved one. The prediction is that within-list comparisons cannot help the worst case, since the adversary can make every neighbour distinct and within-list questions then tell a merge nothing it did not know. On average, with few values, they should help a great deal, since a run of $r$ equal keys costs about $\log_2 r$ comparisons to find and saves up to $r$. The question is where on $k$ the average saving stops paying for the questions that come out unequal. That crossing is the number of values below which a library should look for equal runs before merging, and pdqsort already makes a version of that choice for partitioning.