The spread a merge sort does not have

A distribution computed rather than sampled took quicksort’s comparison count apart pivot by pivot and weighed every outcome, and found on sixty-four keys a mean of 360.706 and a standard deviation of 36.741. It then used those two numbers to answer a practical question — how many runs a sampled mean needs before it can be trusted — and the answer was hundreds at small sizes, falling only slowly as the input grew.

That page was about quicksort because quicksort is the famous randomised sort, and its randomness is the algorithm’s own: the pivot is a coin it tosses. Merge sort tosses no coins. Given an input, it makes exactly one number of comparisons, and a count over every input listed that number for all 40,320 orders of eight keys. Hand it a random input, though, and its count becomes a random variable too, drawn from a distribution over inputs rather than over pivots — and that distribution is the one every benchmark on random data is actually sampling.

This page computes it, exactly, and sets it beside quicksort’s. The two means are a quarter apart. The two spreads differ by a factor that grows without limit, and the reason is visible in the structure of the two recursions before any number is computed.

What one merge leaves over #

Merge sort’s merge takes two sorted runs of $a$ and $b$ keys and compares their front keys until one run is empty. After that the other run’s remainder is copied across with no comparisons at all. So a merge makes $a + b - T$ comparisons, where $T$ is the number of keys still waiting on the other side when the first side runs out. $T$ is at least one: the last key of the merged output is never compared against anything after it.

On a random input, every way of interleaving the two runs is equally likely — there are $\binom{a+b}{a}$ of them — and $T$ is the length of the final stretch of the interleaving that comes from one side. The probability that the last $t$ keys all came from the left run is $\binom{a+b-t}{b} / \binom{a+b}{a}$, and the mirror expression gives the right run. Both can be computed as running products without ever forming a binomial.

For a large balanced merge, the leftover is very nearly geometric. The last key came from one side; the key before it came from the same side with probability about a half; the one before that, a half again. Mean two, variance two, and almost no chance of more than a dozen. That is the entire random content of a merge: a quantity of order one, with a spread of order one, regardless of how many keys the merge handles.

For small merges it is smaller still. A merge of one key against one always leaves exactly one over, so it contributes no randomness at all. A merge of two against two leaves one over with probability two thirds and two with probability one third: variance 0.222. Four against four, 0.640. Eight against eight, 1.106. The variance climbs towards two as the runs lengthen and never passes it.

The step that makes merge sort’s count tractable is that these leftovers are independent. On a random permutation, the order of keys inside the left half, the order inside the right half and the way the two halves interleave are three independent facts. Recursively, every merge in the sort sees an interleaving that is uniform and independent of every other merge’s. So merge sort’s comparison count is a fixed bill — the sum of $a + b$ over every merge — minus a sum of 65,535 independent leftovers at 65,536 keys, and its whole distribution is a convolution of 65,535 small distributions, of which — at a power of two — only sixteen are different.

The distribution, and real runs laid over it #

Convolving is cheap because the top-down split produces at most two distinct run sizes at each level. The count on $n$ keys is the count on $\lfloor n/2 \rfloor$ keys plus the count on $\lceil n/2 \rceil$ keys plus one merge, all three independent, so each distinct size costs two convolutions. At 65,536 keys the array is 2,582 entries long, and the calculation takes milliseconds.

Three routes lead to the same distribution, and all three agree. The convolution gives a probability for every count. The cumulants — mean, variance and third central moment — can instead be summed merge by merge, because cumulants of independent pieces add, and they match the convolution’s to within one part in ten million at every size tried. At eight keys the distribution multiplied by $8!$ must reproduce, integer for integer, the histogram a count over every input obtained by running merge sort on all 40,320 orders. It does. And real runs land where the curve says: 400 of them on 1,024 keys average 8,946.16 against an exact 8,947.15.

The standard deviation at 1,024 keys is 17.683 comparisons, which is 0.20% of the mean. On the same keys quicksort’s is 655, or 5.8% of its mean. The next plate puts both on one axis, at a size where both distributions can be computed exactly.

Two distributions on the same keys #

At sixty-four keys the shapes already say most of it. Merge sort’s count is a tall narrow spike a little to the left of its own worst case. Quicksort’s is a low wide hump whose right tail runs past the whole of merge sort’s range, and past its worst case too: 88% of quicksort’s runs on these sixty-four keys make more comparisons than merge sort can make on any input at all.

The factor of 8.7 between the spreads is not a constant of the two algorithms. It is 8.7 at 64 keys, 37 at 1,024 and 299 at 65,536, and it keeps growing, because the two spreads obey different laws.

One spread grows as n and the other as its square root #

The slopes on the logarithmic plot are one half and one. Merge sort’s spread doubles every time the input quadruples, which is growth as $\sqrt{n}$. Quicksort’s quadruples, which is growth in proportion to $n$. Its variance has a closed form, $7n^2 - 4(n+1)^2 H_n^{(2)} - 2(n+1)H_n + 13n$, which Knuth gives and which agrees here with the recurrence at every size up to 2,048. Its leading term is $(7 - 2\pi^2/3)\,n^2 \approx 0.420\,n^2$.

Merge sort’s follows from the leftovers without any further algebra. Its variance is the sum of the leftovers’ variances. There are about $n/2^{k+1}$ merges of $2^k$ keys a side, and each contributes a variance that climbs from 0 for the smallest towards 2 for the largest, so the total is $n$ times a convergent sum — about $0.31\,n$. The square root of $0.31\,n$ at 65,536 keys is 142, and that is the number on the plate.

The laws are different because the two sums are different kinds of sum. Merge sort’s randomness is a sum of many pieces, each of order one and each independent of the rest. Quicksort’s randomness is not like that at all. Its first pivot decides how the whole of the rest of the work divides. A first pivot landing at the quarter point instead of the middle changes the expected remaining cost by an amount proportional to $n$, and nothing later averages that away, because nothing later is independent of it.

Where in the recursion the spread is made #

That difference can be measured rather than argued. Variances of independent pieces add, so merge sort’s variance splits exactly into what each level of merges contributes. Quicksort’s splits by the law of total variance: the share its first pivot decides is the variance, over that pivot, of the expected count given it; the rest is the same split one level down, averaged over the first pivot.

Quicksort’s spread is made at the top and merge sort’s is made at the bottom. One random choice — the first pivot — accounts for a third of quicksort’s whole variance at 4,096 keys, and 33.4% of it at 65,536. The top three levels, seven pivot choices out of about four thousand, account for 71%.

The two thirds between successive levels has a one-line explanation. A subproblem of $m$ keys contributes, at its own top level, a variance proportional to $m^2$, because its pivot moves its expected cost by an amount proportional to $m$. One level down, its two children have sizes $U$ and $m - 1 - U$ with $U$ uniform, and the expected sum of their squares is two thirds of $m^2$. So each level holds two thirds of the variance of the level above, a geometric series that puts most of the weight within a few levels of the root.

Merge sort’s shares run the other way. The final merge of two 2,048-key halves is the largest single merge and contributes a variance of two, which is 0.16% of the total, because there is only one of it. Each level down has twice as many merges and each has a variance only slightly below two, so the shares double level by level — until the merges get small enough that their leftovers stop being random. The peak is merges of four keys against four, and below that it falls away to nothing, because a merge of one key against one is not random at all.

That is the structural reason one spread is $\sqrt{n}$ and the other $n$. A sum dominated by a few large terms has a spread the size of its largest term. A sum of many small, independent, comparable terms has a spread the size of the square root of their number.

A bell, and a tail that does not go away #

The same distinction decides the shape. A sum of many small independent pieces tends to a normal curve — symmetric, with thin tails — and the rate at which it gets there can be read off its skewness, the third central moment divided by the cube of the standard deviation. A symmetric bell has skewness zero.

Merge sort’s skewness is negative because each merge’s leftover has a right-hand tail — occasionally a merge leaves seven or eight keys over — and the leftover is subtracted from the bill, so the tail points left. It halves every time the input quadruples, which is the $1/\sqrt{n}$ rate at which a sum of independent pieces loses its asymmetry. By 8,192 keys it is −0.030, and the distribution is a bell for every practical purpose. Flajolet and Golin proved in 1994 that the limit is exactly normal; the plate shows the approach rather than the limit.

Quicksort’s skewness does not go to zero. The third moments here come from the same recurrence over the pivot’s rank that gave the variance, checked against the exact distribution at 8, 32 and 64 keys, and they settle near 0.86. That the limit law is not normal at all is a theorem of Régnier and Rösler from around 1990: normalised by $n$, quicksort’s comparison count converges to a fixed skewed distribution of its own. The mechanism is the one the previous plate drew. A count decided mostly by a few early choices inherits their shape, and an unlucky first pivot is a large, lopsided event that no amount of later averaging can make symmetric.

For merge sort, the practical meaning of a bell is that the standard deviation is the whole story. Four standard deviations cover all but one run in fifteen thousand. For quicksort the long right tail means a standard deviation understates how far the bad runs go, and on average is not a number made that point about quicksort by sampling it. Here it is a property of the limit, not an accident of the sample.

What a benchmark needs to run #

A distribution computed rather than sampled turned quicksort’s exact moments into a count of runs: how many independent runs a sampled mean needs to land within a stated fraction of the true mean 95% of the time. The rule is $(1.96 \cdot \sigma / (p \cdot \mu))^2$, and it depends only on the coefficient of variation $\sigma/\mu$. That ratio is where the two laws above show up as a working difference.

Merge sort’s coefficient of variation falls like $1/(\sqrt{n}\log n)$: the spread grows as $\sqrt{n}$ and the mean as $n \log n$. Quicksort’s falls only like $1/\log n$, since both its spread and its mean are close to proportional to $n$ and only the logarithm in the mean separates them. At 65,536 keys merge sort’s is 0.015% and quicksort’s is 3.4%.

Counting instead of timing made every count here reproducible to the last digit on a fixed input. On random inputs the question is how much one input can stand for all of them, and the answer differs between the two sorts. So from 256 keys up, one run of merge sort on a random input measures its mean to within one per cent, and from 16,384 keys to within a tenth of one per cent. A single run is not a sample from merge sort’s distribution in any sense that matters; it is a measurement of its mean. One run of quicksort at 65,536 keys is a draw whose standard deviation, 42,470 comparisons, is more than three times the whole of that one per cent.

That changes what a comparison between the two can say. The two means at 65,536 keys stand in the ratio 1.312: quicksort with a random pivot makes 31% more comparisons than merge sort, on average. A benchmark that ran each once and reported the ratio could get anything from 22% to 40% more at two standard deviations either side, and all of that uncertainty would be quicksort’s. A result the size of its own noise is the page on this collection about reporting a difference without its spread. The lesson here is sharper: of two algorithms in a comparison, one may need a spread and the other not.

A variance that wobbles with the logarithm #

Merge sort’s variance was described above as about $0.31\,n$. Computed exactly at many sizes, it is not a constant times $n$.

At every power of two the variance is $0.307\,n$. Between powers of two it rises by almost a fifth and comes back, and the arch repeats exactly in every doubling. The variance is $n$ times a periodic function of $\log_2 n$, not $n$ times a constant.

The cause is the split. When $n$ is a power of two every merge is perfectly balanced, $2^k$ against $2^k$. Between powers of two the top-down split produces merges of unequal sizes at some levels — 21,870 against 21,870 at the top, but runs of different lengths lower down — and an unbalanced merge’s leftover has a different distribution from a balanced one’s. How many levels are unbalanced, and how badly, depends on where $n$ sits between powers of two and on nothing else, so the pattern repeats in every doubling. Flajolet and Golin worked out the same oscillation analytically, as a periodic function with a Fourier series; the plate is that function, drawn from counts.

The mean has the same wobble, and it has consequences for anybody fitting a curve to merge sort. Fitting a class to measurements granted merge sort its $n \log n$ class by fitting counts across three orders of magnitude, and the fit holds. But the second term is not a constant times $n$. It is between $-1.240\,n$ and $-1.264\,n$ depending on where the size falls, so a fit of $a\, n \log n + b\, n$ to sizes that happen to be powers of two will find a different $b$ from a fit to sizes that happen not to be. Neither is wrong. They are two readings of one periodic function, taken at different points in its period.

The worst case as a place nothing visits #

Merge sort’s worst case is the number most often quoted about it: at most $n\lceil\log_2 n\rceil - 2^{\lceil\log_2 n\rceil} + 1$ comparisons, which at 65,536 keys is 983,041. It is reached when every merge leaves exactly one key over. The best case, 524,288, comes when every merge takes one side whole before touching the other.

On random input the count lives in a band a thousand comparisons wide, inside a range of 458,753. The worst case is 17,333 comparisons above the mean. That is only 1.8% of the mean, and it is 122 standard deviations. The probability that a random input produces it is the product of every merge’s chance of leaving exactly one key over, which is about $10^{-7189}$.

None of that makes the worst case unreachable. Merge sort is deterministic, and its distribution is over inputs, not over anything it chooses. An input built to make every merge leave one key over produces 983,041 comparisons every time it is sorted. The worst case found by climbing found merge sort’s worst case at sixty-four keys on every attempt, by local search. The band on the plate is a statement about random input, and it says nothing about an adversary.

This is the respect in which the two distributions on this page are not the same kind of object. Quicksort’s spread is its own: on any fixed input its random pivot gives the same distribution, so no adversary can remove it, and no benchmark can avoid it. That is the bargain what randomising the pivot buys described. Merge sort’s spread belongs to the input. On any one fixed input merge sort has no spread at all, and the sort whose count has no distribution — Batcher’s network, which ignores the input entirely — is the extreme of the same idea. What merge sort offers is not a guarantee against bad luck. It offers something benchmarks rarely get: on inputs drawn at random, the count is a constant to within a fifth of a per cent from a thousand keys up, and one measurement is enough.

Still open: the spreads of the sorts whose pieces are not independent #

Merge sort’s spread came out small because its randomness split into independent pieces, and that independence is a special property of a merge on a random permutation. The same question can be asked of every other deterministic sort here, and for most of them the pieces are not independent.

Insertion sort is the easy case and makes a sharp prediction. Its comparison count is the number of inversions plus a correction of at most $n - 1$, and the distribution of inversions over random permutations is known exactly. Its generating function is the product of $1 + x + \cdots + x^{k-1}$ over $k$ up to $n$, which is again a sum of independent pieces, one per key. So its variance should sit within a few per cent of $n(n-1)(2n+5)/72$, the variance of the inversions, and its spread should grow as $n^{3/2}$ against a mean growing as $n^2$ — a coefficient of variation falling as $1/\sqrt{n}$, faster than quicksort’s and slower than merge sort’s.

Heapsort is the interesting one. Its comparisons are spent in sift-down paths whose lengths depend on the heap’s current shape, and the shape after each extraction depends on every extraction before it. There is no decomposition into independent pieces, and no closed form is known to this collection. The measurement that follows computes the distribution exactly at small sizes by enumerating every input, samples it at large ones, and fits the growth exponent of the standard deviation. The prediction to test is that heapsort’s spread grows as $\sqrt{n}$ like merge sort’s, because its dependence is local. If it grows faster, then the dependence between extractions is carrying randomness over long distances. That would mean a heap remembers the order of its input for longer than its construction suggests.