The frontier between time and space

The question every summary of sorting is trying to answer is which one to use, and the summaries answer it with a table of complexity classes, from which the reader is expected to extract a ranking that the table does not contain.

With two measured resources instead of one class, the question has a precise answer, and the answer is not a ranking. It is a set.

An algorithm is on the Pareto frontier if nothing else is at least as good as it on both axes and strictly better on one. Everything not on the frontier is dominated: there is something that beats it on comparisons and on space, so there is no workload, no weighting of the two costs, no circumstance under which it is the right choice by these measures.

At $n = 8{,}192$ on random input, five of the ten sorts here are on the frontier and five are dominated.

The frontier, at $n = 8{,}192$ on random input #

Reading down the frontier from left to right is reading a price list. Merge sort is the cheapest in comparisons and costs the array again. Giving up 14% of comparisons buys nothing here — the hybrid saves four slots — so that pair is nearly a tie. Giving up a further 10% buys the entire buffer: quicksort’s 29 slots against merge sort’s 8,207, for 121,133 comparisons against 96,140. Giving up 33% more buys the last 28 slots: Shellsort holds one.

The three quadratic sorts are dominated for the reason everybody expects. Shellsort matches their space exactly and does two orders of magnitude less comparing.

The two interesting dominations are the other two.

Heapsort is dominated by Shellsort #

Heapsort’s whole case is that it is the algorithm with no trade-offs: $\Theta(n \log n)$ in the worst case, $\Theta(1)$ auxiliary space, no bad inputs, no randomness. It is the fallback inside introsort for exactly that reason.

At $n = 8{,}192$ on random input it does 187,705 comparisons in one slot. Shellsort does 161,614 comparisons in one slot. Fewer comparisons, identical space, so heapsort is off the frontier.

Three things have to be said about that immediately, and they are the reason this result is interesting rather than a mistake.

It is a statement about comparisons and slots, and nothing else. Heapsort’s real weakness is its access pattern — the sift jumps by powers of two and the modelled miss counts are among the worst on the site — and its real strength is a worst-case guarantee. Neither axis on this plot is either of those things. A frontier is only as informative as its axes, and this one has two.

Shellsort has no proven class. Its complexity for the gap sequence used here is an open problem, and the “constant” measured for it drifts by 69% over six doublings. Heapsort’s $\Theta(n \log n)$ is a theorem and holds on every input. Trading a theorem for 14% fewer comparisons at one size is a trade most people should decline, and the frontier cannot express “and this one is guaranteed”.

It reverses on other inputs. At $n = 4{,}096$ on reversed input, Shellsort does 51,477 comparisons and heapsort 82,304 — the gap widens. On nearly-sorted input Shellsort does 32,147 against heapsort’s 88,845 — nearly a factor of three. Heapsort’s remarkable property is that it does not care what the input is, and on this plot that property looks like consistently losing.

So the honest reading is not “use Shellsort”. It is: by these two measures, at these sizes, heapsort is not on the frontier, and everything that justifies using it anyway lives on axes this plot does not have. That is a useful thing to be able to say precisely, and it is the kind of statement a complexity table cannot make at all.

Quicksort’s first-element pivot is dominated by its random one #

The other domination is cleaner and has no caveats.

First-element quicksort: 127,140 comparisons, 35 slots. Random-pivot quicksort: 121,133 comparisons, 29 slots. Fewer of both, on random input — the input most favourable to the deterministic rule.

And on any other input the first-element rule is catastrophic in both resources at once: 8,386,560 comparisons and 4,097 slots on a sorted array of 4,096, against 56,469 and 22 for median-of-three.

The reason this is worth pointing out separately is that it is a domination with no trade being made. The usual argument for a deterministic pivot is that it avoids the cost of generating random numbers, which is a cost neither of these axes measures. Every axis that is measured says the random pivot is better, including on the input the deterministic rule is chosen for.

The frontier is a property of the input #

Change the input and the picture rearranges completely. At $n = 4{,}096$:

Random input. Five on the frontier: merge, hybrid, quickRandom, quickMedian3, Shellsort. A genuine spread of choices from 4,110 slots down to one.

Reversed input. Three on the frontier: merge sort at 24,576 comparisons and 4,110 slots, the hybrid at 47,104 and 4,106, Shellsort at 51,477 and 1. Both quicksorts have fallen off — median-of-three does 85,871 comparisons here, more than Shellsort in more space.

Nearly sorted input. One. Insertion sort does 4,713 comparisons in one slot, and nothing on the site beats it on either axis. The frontier collapses to a single point and every other algorithm is dominated by the simplest one there is.

Sorted input. Two, and they are insertion sort and bubble sort at 4,095 comparisons and one slot apiece. Everything else is dominated, including merge sort by a factor of six and heapsort by a factor of twenty.

A frontier with one point on it is not a trade-off, it is an answer, and “on nearly sorted data, use insertion sort” is genuinely the whole of the advice for that case. That the same plot gives five answers on random data and one on nearly-sorted data is the input-distribution problem rendered as a change in the shape of the answer rather than in its value.

What a frontier is good for, and what it is not #

Three uses, in increasing order of how much they justify drawing one.

It eliminates. Half the algorithms here are dominated on random input, and eliminating half the candidates without needing to know anything about the workload is worth more than ranking the other half. A dominated algorithm is not a worse option; it is not an option.

It prices the trade. The gap between adjacent frontier points is the exchange rate. Between quicksort and Shellsort at $n = 8{,}192$: 28 slots for 40,481 comparisons, or about 1,450 comparisons per slot. That number is the thing an engineer actually needs and no complexity table contains it.

It shows when there is no trade. One point means the question is settled; five means it is not. A summary that always produces a recommendation cannot tell the two situations apart, and they are the two situations that call for the most different responses.

What it is not is a decision procedure. Two axes were chosen and there are at least four more that matter — modelled cache misses, worst-case guarantees, stability, whether the algorithm can be interrupted or run in parallel. Adding an axis can only add points to the frontier, never remove them, so every one of these five would still be on it and some of the dominated five would join them. The frontier is a lower bound on the set of reasonable choices.

Two more sizes, four doublings apart, say that the membership is a property of the algorithms rather than of where the sweep happened to stop.

A third axis, and what it does not change #

The obvious objection to a two-axis frontier is that there are more than two axes, and the obvious response is to add one and see.

Adding modelled cache misses as a third axis, at $n = 4{,}096$ on random input:

Nothing changed. The same five are on it and the same five are off it.

That is a genuinely informative negative result and it needs both halves reported. Adding an axis can only ever add points to a frontier — a new axis gives a dominated algorithm a new way to be uniquely good, and gives nobody a new way to be beaten. So a third axis that adds nothing means every dominated algorithm here is dominated on the new axis too, by the same competitor.

Look at the two dominations from the previous sections and it is easy to see why. First-element quicksort is beaten by the random-pivot version on comparisons (57,431 to 54,243), on space (29 to 28) and now on misses (3,713 to 3,423) — three for three. Heapsort is beaten by Shellsort on comparisons and ties on space, and its miss count is 15,409 against Shellsort’s 9,305, so the third axis makes its position worse rather than rescuing it.

Two things worth saying about that, because a null result invites over-reading in both directions.

It is a result about this size. At $n = 512$ every algorithm’s working set fits inside the modelled cache and the miss rates are all between 0.2% and 0.4% — the axis carries no information at all, and a frontier including it would be reporting noise. At $n = 32{,}768$ the miss rates separate to between 2.7% and 7.6%, and the axis is doing real work. The measurement above sits above the cliff and would look different below it.

It does not mean the axis is redundant. It means that on these ten algorithms the miss count is well predicted by the other two. Heapsort is the exception the pattern proves: it is the algorithm whose real weakness is locality, and the reason the third axis does not rescue it is that it is already off the frontier for a different reason.

The honest summary is the one this whole site keeps arriving at. A frontier is only as good as its axes; adding a plausible third axis here changed nothing; and that is evidence about ten sorting algorithms rather than a claim that two axes are enough in general.

What a frontier says about a default #

Standard libraries pick one algorithm, and the frontier explains what kind of decision that is.

Almost all of them pick some variant of quicksort — introsort in C++, pdqsort in Rust, a dual-pivot quicksort in Java for primitives. On the plot that is the middle of the frontier: 121,133 comparisons and 29 slots at $n = 8{,}192$, against merge sort’s 96,140 comparisons and 8,207 slots at one end and Shellsort’s 161,614 and 1 at the other.

The middle of a frontier is a defensible place for a default and it is not a neutral one. It says: memory is worth something but not everything, and comparisons are worth something but not everything, at an exchange rate of roughly 1,450 comparisons per slot. A library that chose merge sort would be saying memory is nearly free; one that chose Shellsort would be saying it is nearly priceless.

Java’s split is the giveaway. It sorts primitives with quicksort and objects with a merge sort, because sorting objects requires stability — equal elements keeping their relative order — and no algorithm at the low-space end of this frontier is stable. That is a third axis, it is binary rather than continuous, and it moves the default all the way across the plot for one of the two cases. The frontier drawn here has nothing to say about it, which is a fair summary of what two axes can and cannot settle.

The exchange rate is not one number #

The frontier is described above as a price list, and the price is quoted once — 1,450 comparisons per slot, between quicksort and Shellsort. That is the rate at one end. At the other end it is entirely different, and the ratio between them is the most useful number this plot produces.

At $n = 8{,}192$, walking the frontier from the space-hungry end:

Merge sort to quicksort. 8,178 slots saved for 24,993 extra comparisons — about 3.1 comparisons per slot.

Quicksort to Shellsort. 28 slots saved for 40,481 extra comparisons — about 1,450 comparisons per slot.

A factor of nearly five hundred between the two ends. The frontier is not a line with a slope; it is a curve that is nearly flat where the space is large and nearly vertical where it is small, and the practical consequence is immediate: the first eight thousand slots are almost free and the last twenty-eight are ruinously expensive.

That settles a question the plot otherwise leaves open. A system under memory pressure should give up merge sort’s buffer without hesitation, because doing so costs three comparisons per slot recovered. The same system should not go on to give up quicksort’s twenty-nine slots, because those cost five hundred times more each and twenty-nine slots is not a quantity anybody is short of.

And the rate is not stable in $n$. At $n = 4{,}096$ the two rates are 2.5 and 550; at $n = 8{,}192$ they are 3.1 and 1,450. The high-space rate grows slowly — it is a ratio of two comparison counts, both $\Theta(n\log n)$, over a slot count that is $\Theta(n)$, so it drifts like a logarithm. The low-space rate grows like $n\log n$, because the comparison gap grows and the slot gap is a constant handful.

So the low-space end of the frontier gets steeper without limit as the problem grows, and a decision to run in constant space is one whose price rises with the input. That is the opposite of the intuition that space matters more at scale — space matters more at scale, and giving up the last of it costs more at scale too.

Exact counts manufacture non-dominance #

The headline says five algorithms are on the frontier and it is worth reading the table again with a practitioner’s eye, because two of the five are a single choice.

Merge sort holds 8,207 slots and merge sort with a cutoff holds 8,203. Four slots apart, on structures of eight thousand. Neither dominates the other, so both are on the frontier — the hybrid is strictly better on space by an amount nobody could measure and strictly worse on comparisons by 14%.

That is dominance working exactly as defined and producing an answer nobody wants. A frontier computed from exact integer counts treats a difference of four as a difference, so any pair of algorithms differing by a rounding error on one axis is reported as an incomparable pair, and the frontier is padded with distinctions that are not distinctions.

The repair is to say what counts as a difference before computing the set. Rounding each axis to, say, two significant figures before testing dominance collapses those two points into one, and the frontier at $n = 8{,}192$ becomes four positions rather than five: the merge family, the quicksort family, Shellsort, and nothing else.

Which is the number a reader should carry away. Four genuinely distinct positions, spanning a factor of eight thousand in space and a factor of 1.7 in comparisons, with the exchange rate between adjacent pairs varying by five hundred times — and five of the ten algorithms not on the list at all.

The general caution is worth having beyond this plot. Dominance is a crisp relation over exact numbers and a fuzzy one over quantities anybody cares about, and a Pareto set computed without a tolerance reports the crispness rather than the caring.

The same shape, one level down #

This is not the first Pareto set on the site. Choosing a dynamic array’s growth factor is the identical question with the identical answer: amortised cost on one axis, wasted allocation on the other, no factor best on both, and real implementations landing at 1.125, 1.25, 1.5 and 2 because they weight the axes differently.

The two are worth putting side by side because of the difference in scale. A growth factor moves the amortised append cost between 2.0 and 9.9 units, and every choice is defensible. A sorting algorithm moves the peak space between 1 slot and $n$, and some of the choices are not defensible at all.

What is the same is the structure of the honest answer. In both cases the received wisdom is a single recommendation — “double the array”, “use quicksort” — and in both cases the recommendation is a point on a frontier that somebody chose on behalf of a workload they had not seen. Drawing the frontier does not make the choice; it makes visible that a choice was made.