The floor a merge cannot reach

Every floor in this field so far has come from counting outcomes. The floor under every comparison sort counts $n!$ orderings and takes the logarithm. It then shows that merge sort sits a couple of per cent above it, and that nothing can sit below.

How close anything gets to the floor took the argument apart one merge at a time. A merge of a $p$-key run with a $q$-key run has $\binom{p+q}{p}$ possible interleavings, the logarithms of those counts add up to $\log_2(n!)$, and so each merge has a floor of its own. It measured merge sort against those per-merge floors and found the waste spread across the tree, 4.076 comparisons in the largest merge and nothing at all in the smallest.

That measurement left a question it could not ask. Is a merge’s own floor something a merge can actually reach? The count says $\lceil \log_2 \binom{m+n}{m} \rceil$ comparisons are necessary. It does not say they are enough. For sorting, nothing closes the gap in general. For merging, the whole game is small enough to solve.

Solving the merge #

An algorithm merging a sorted list $a$ of $m$ keys into a sorted list $b$ of $n$ keys needs one fact about each $a_i$: how many keys of $b$ are smaller. Call it $p_i$. Because both lists are sorted, $p_1 \le p_2 \le \dots \le p_m$, and each such sequence is one interleaving.

Whatever an algorithm has learned can be written as a range for each $p_i$. Comparing $a_i$ with $b_j$ cuts that range at $j$, and the cut spreads: if $a_i$ is below $b_j$ then so is every earlier key of $a$, and if it is above then so is every later one. A state of knowledge is two sequences of bounds. The fewest comparisons that still guarantee the answer from a state is one more than the best question’s worse outcome, the same minimax every pair must be asked used for graphs, and it is computed over every reachable state. At seven keys a list that is 2,760,615 states. A second solver checks the first at small sizes. It works on explicit sets of the interleavings still possible and shares no representation with the first, and the two agree.

The first row is binary search. Placing one key among $n$ takes $\lceil \log_2(n+1) \rceil$ comparisons and the floor is the same number, because the $n+1$ positions are the outcomes and a binary search halves them each time. A single key can always be merged at the floor.

The second row already misses. Two keys into four sorted keys have $\binom{6}{2} = 15$ interleavings, and four comparisons could tell sixteen apart. The solve needs five. At six the same happens again, 28 interleavings and a floor of five against six needed. The whole second row matches a closed form for two keys, published in the early 1970s. That formula is checked against the solve at every $n$ from 2 to 10, as a check on the solver rather than on the formula.

Fifteen outcomes and no even question #

The smallest miss shows what goes wrong in all of them. Two keys into four have fifteen interleavings. Four comparisons can tell sixteen outcomes apart, but only if the first one leaves at most eight on each side, the second at most four, and so on down. So the question is whether any first comparison divides the fifteen that evenly.

None does. There are eight possible first comparisons, each key of $a$ against each key of $b$, and they divide the fifteen interleavings as 5 and 10, 9 and 6, 12 and 3, 14 and 1, 1 and 14, 3 and 12, 6 and 9, and 10 and 5. The most even leaves nine on one side. Nine outcomes need four more comparisons, so every first choice ends at five.

The splits are uneven because of what a comparison between $a_i$ and $b_j$ asks. It asks whether $p_i$ is below $j$, and the number of interleavings on each side of that cut is fixed by how many ways the other key can sit around it. A key near the end of one list against a key near the start of the other is nearly always decided in one direction. A key in the middle against a key in the middle comes closest to even, and with two keys and four positions the closest available is nine to six. Counting assumes a question that cuts the outcomes in half. The list structure offers only the cuts that the positions allow.

The misses spread with size. Up to six keys a list, every case with both lists at four or more keys except four into four misses by one, and the diagonal stops meeting the floor at five keys each. The counting floor is a floor. It is not the answer, and the gap is structural. Counting treats every comparison as able to split the remaining outcomes in half. A comparison between two particular keys usually cannot.

Why equal lengths are the worst #

On the diagonal the solver finds $1, 3, 5, 7, 9, 11, 13$: exactly $2m - 1$ at every size it reaches. That is also what the textbook merge makes on its worst input, the one that walks both lists to the end. The obvious algorithm is exactly optimal on equal lengths, and the counting floor is what fails to see it.

The reason is short enough to draw.

That is an adversary argument, the kind the adversary who hides the edge used for connectivity: no counting, just an input on which any skipped question leaves two answers standing. It works for every $m$, so $2m - 1$ is proved at every size, not only at the sizes the solver reaches. The solver is checking the argument, and it agrees at all seven sizes it can reach.

What counting predicts for the same input is $\log_2 \binom{2m}{m}$. By Stirling’s approximation, $\binom{2m}{m}$ is close to $4^m / \sqrt{\pi m}$, so the floor is $2m - \tfrac12 \log_2(\pi m)$ plus a vanishing correction. The adversary demands $2m - 1$. The difference grows.

The gap is small in absolute terms: five comparisons out of eight thousand at 4,096 keys a list. It is also unbounded, and its shape is the interesting part. A logarithmic floor that is off by a logarithm of the length means counting has misjudged something basic about the problem. It has. It counts the outcomes but not how evenly a single comparison can divide them. When the lists interleave closely, a comparison near the middle of one list mostly confirms what the neighbouring comparisons already implied. The questions a sort asks twice found the same kind of comparison inside insertion sort: a question that is new, and still worth far less than a bit.

Four merges against the solved optimum #

With the exact optimum known, real merges can be scored against it rather than against a floor that may be out of reach. Four are measured on every interleaving at five sizes, with every output checked sorted.

The textbook merge compares the two heads and emits the smaller. Binary insertion places each key of the shorter list by binary search, starting where the previous key went. Galloping probes ahead in steps of one, two, four and so on, then binary-searches the bracket it finds, which is the move when galloping pays measured inside a library sort. Hwang and Lin’s method, from 1972, compares the shorter list’s last key against a key $2^t$ from the end of the longer list, with $t = \lfloor \log_2(n/m) \rfloor$. That discards $2^t$ keys with one question, or places the key with $t$ more.

Nothing is optimal everywhere, and the losses have different sources. The textbook merge is optimal on equal lengths and wastes six of thirteen comparisons at two into twelve. It asks about the long list one key at a time, when the answer is nearly always “keep going”. Binary insertion is the reverse. It is close at two into twelve and needs fifteen at five into five, because a binary search over what remains of $b$ does not know that the next key of $a$ is probably just past the previous one.

The two failures are mirror images, and each is a choice about which question to ask first. The textbook merge always compares the two heads, a question that splits the outcomes evenly only when the lists are the same length. Binary insertion always compares against the middle of what remains, which splits evenly only when the shorter list has a single key. Neither asks the question that the two lengths call for, and the grid above shows that asking the most even question available is still not enough to reach the floor.

Galloping sits between the two and is never the best of the four here. Its extra cost is the probing: to place a key $d$ positions away it spends about $2 \log_2 d$ comparisons where a search that knew $d$ would spend $\log_2 d$. Hwang and Lin is optimal at three of the five sizes and one comparison over at the other two. It is the only one of the four that adjusts to the ratio of the two lengths, and it is the only one that is never badly wrong.

The average floor is nearly exact #

Everything so far is about the worst interleaving. Merge sort’s per-merge accounting in how close anything gets to the floor was an average over random inputs, and the average has a floor too. Over uniformly random interleavings, no algorithm can average fewer than $\log_2 \binom{m+n}{m}$ comparisons, the same count without the ceiling. The same solve can weight each state by how many interleavings it still allows and minimise the expected number of questions instead of the worst.

The average optimum lies within a tenth of a comparison of the counting floor at every length. The worst case, with the same lengths and the same floor, misses by up to 1.29. So the floor is nearly exact on average and it is the worst case that counting gets wrong. That is the opposite of what the ceiling on a worst-case floor would suggest.

The reason is the same uneven split. An algorithm cannot divide the remaining interleavings in half with one comparison, but it can come close, and an average forgives a question that splits 55 to 45. The worst case forgives nothing, since the adversary always takes the larger side. Over many questions a small imbalance becomes a whole comparison in the worst case and a tenth of one on average.

That also sorts the waste how close anything gets to the floor measured in merge sort into what could be avoided and what could not, width by width. That essay found merges of four keys wasting 0.078 comparisons each and merges of eight wasting 0.261, against the bits their interleavings carry. Solved exactly on equal halves, the numbers look like this:

• Two and two. Floor 2.585, best possible average 2.667, textbook merge 2.667. The textbook merge is the best possible merge of that size, and all of its 0.082 excess is unavoidable.
• Four and four. Floor 6.129, best 6.229, textbook 6.400. Of an excess of 0.271, 0.099 is unavoidable and the rest, 63%, belongs to the textbook merge.
• Six and six. Floor 9.852, best 9.963, textbook 10.286. Of 0.434, 74% is recoverable.
• Seven and seven. Floor 11.745, best 11.862, textbook 12.250. Of 0.505, 77% is recoverable.

The unavoidable part hardly moves, 0.08 to 0.12 across those sizes. The textbook merge’s own share grows with the merge. So the eleven per cent of merge sort’s excess that the earlier table put in its four-key merges could not be removed by any merge at all, and the share that could be removed grows with the width of the merge. The recovery would need a merge far more complicated than comparing two heads, which is one reason merge sorts do not attempt it.

A thousand to one #

The exact solves stop at a few keys a list, and the ratio between the two lengths is where the four merges really differ. With 64 keys in the short list and random interleavings, the comparisons each merge makes can be set against the counting floor up to a long list of 65,536 keys.

The four curves say something the small grid could only hint at. The textbook merge is within 2% of the average floor on equal lengths and 89 times over it at a thousand to one. Binary insertion is 2.6 times over on equal lengths and drifts towards the floor as the ratio grows, reaching 1.29 at the right edge. Galloping starts near the floor and climbs towards a factor of two. That is the $2\log_2 d$ against $\log_2 d$ of its probing showing through, once the gaps between keys become the dominant cost.

Hwang and Lin stay within 3% of the floor at every ratio, and at 1.1% or less from sixty-four to one upwards. It is the algorithm that asks the question counting assumes: one that splits the remaining possibilities as evenly as the two lengths allow. Its first comparison is chosen by the ratio, and that choice is most of what separates it from the other three.

What the solve settles and what it leaves #

Five things here are exact.

The worst-case optimum is computed for every pair of lengths up to six keys each and for equal lengths up to seven, and it agrees with a second solver that shares no representation. It reproduces $\lceil \log_2(n+1) \rceil$ for a single key and the published closed form for two keys. On equal lengths it finds $2m - 1$ at every size it reaches, which the adversary argument proves at every size. The counting floor is missed in 8 of 21 cells, and the miss on equal lengths grows as $\tfrac12 \log_2(\pi m) - 1$. The average optimum is within 0.111 comparisons of the counting floor at every length merged into six.

Three things are not settled.

The worst-case optimum between the edges. For lengths beyond the solver’s reach and ratios other than one, the exact optimum is known only in special cases. Hwang and Lin’s method is known to stay within about $m$ comparisons of the counting floor, and at the sizes solved here it is within one of the optimum. That is not a proof that it is within one everywhere.

The average at large sizes. A gap of 0.111 is measured at six into six. Whether the best average stays a bounded distance above the floor as lengths grow, or creeps up as the worst case does, is not something six keys can show. The ratio plate is an upper bound from one algorithm, not the optimum.

Merges inside a sort. Merge sort does not merge random interleavings independently. The runs at each level come from the level below, and an adaptive sort decides its merge order from the data. Two floors that can be added found that floors from different parts of a problem can add. Whether per-merge floors add into a floor for a whole sort that uses a different merge at each size is a separate question.

Still open: the merge that sorts ties #

Every key here is distinct, and that is the assumption most worth dropping. The floor when the values repeat showed that repeated values lower the sorting floor by more than half, since equal keys need no relative order. A merge of two runs drawn from a few distinct values has far fewer outcomes than $\binom{m+n}{m}$. Keys of $a$ equal to a key of $b$ can go on either side, so the question is where the runs of equal values begin and end, not where each key goes.

The measurement that follows sets up the same game for lists over an alphabet of $k$ values. A state of knowledge is then a range for each boundary between value classes, not for each key. The solve at small sizes finds the exact worst-case and average optima as $k$ falls from $m + n$ to two. The prediction is that the counting floor is 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 also rarer, so it is exactly the kind of question an adversary can refuse to give. If that holds, then the merges that treat equality as a third outcome, which most library merges do not, are the only ones that can approach the lower floor at all.