A run is a property of the input

There is a weakness in this collection that has been present since the first essay and has never been named. It is the word nearly.

INPUTS.nearlySorted produces an array of the integers 0 to n−1 with n/20 adjacent pairs exchanged, at a stated seed. Every claim on this site about adaptive behaviour — insertion sort’s, bubble sort’s, Timsort’s — has been made against that array. It is reproducible, it is stated, and it is not a measurement of anything. It is a recipe. Change the divisor from 20 to 5 and every one of those claims is about a different input, and nothing in the vocabulary would notice.

That is tolerable when the claim is qualitative. It stops being tolerable the moment an algorithm’s bound is stated in terms of the input’s shape, and Timsort’s is:

$$O(n + n \log r)$$

where $r$ is the number of natural runs. There is no way to test that with an input kind called “nearly sorted”, because “nearly sorted” does not have an $r$. It has an $r$ for one seed at one size, which is an anecdote.

Making the shape a number #

Two measures of how far an input is from sorted have been used for as long as anyone has analysed sorting, and they are not the same measure.

Runs. The number of maximal ascending or descending stretches. Sorted input has one; reversed input has one; an array where every adjacent pair has been exchanged has n/2.

Inversions. The number of pairs $(i, j)$ with $i < j$ and $a_i > a_j$. Sorted input has none; reversed input has $\binom{n}{2}$, the most possible; an array where every adjacent pair has been exchanged has n/2.

Both are exactly countable. Runs by one scan; inversions by a merge sort that counts, in $\Theta(n \log n)$, which is affordable at every size drawn here.

The two extremes on that plot are the argument. Take 1,024 elements as two ascending halves in the wrong order — the top half first, then the bottom half. That has 2 runs and 262,144 inversions, a quarter of the maximum. Now take the same 1,024 elements with every adjacent pair exchanged: 512 runs and 512 inversions.

Insertion sort’s cost is $\Theta(n + I)$ where $I$ is the inversions, so it does essentially nothing to the second array and quadratic work on the first. Timsort’s cost is in the runs, so it does essentially nothing to the first array and full merge work on the second. The two measures rank these two inputs in opposite orders, and any single word that covers both — “nearly sorted”, “almost in order”, “partially sorted” — is hiding a factor of five hundred in whichever direction the reader was not thinking about.

Sweeping the second parameter #

With a number for the shape, the bound becomes testable in exactly the way the graph field’s two-parameter bounds are testable: hold one parameter, sweep the other, and see whether the predicted shape describes the measurement. Two parameters, one bound established the method on $V$ and $E$. Here it is $n$ and $r$, and the second parameter belongs to the input rather than to the structure.

withRuns(n, r) builds an input containing exactly $r$ natural runs, verified rather than assumed — the gate builds them across a range of sizes and requires the measured run count to be the requested one.

Timsort at n = 8,192 costs 8,191 comparisons at $r = 1$ and 49,518 at $r = 181$, and $n + n \log_2 r$ tracks the measurement to within the site’s usual tolerance across that range. Merge sort’s line is horizontal: 53,790 comparisons at every $r$, because merge sort does the same work on every input of a given size and always has.

That flat line is worth a sentence of its own. It is what “not adaptive” looks like once there is an axis to draw it against, and it is also why merge sort is better than Timsort at $r = 512$ and worse at $r = 1$. The adaptive algorithm is not uniformly better. It is better in a region, and the region is now something a figure can show rather than something an essay has to assert.

Where the second parameter comes from is not obvious either #

There is a temptation, once an axis exists, to treat it as the axis. It is worth resisting for one measurement.

At $r = 2$ the sweep costs Timsort 16,382 comparisons — exactly $2(n-1)$, the largest a single merge of two equal halves can cost. At $r = 6$ it costs 32,760, which is four times the $r=1$ figure for six times the runs. The bound predicts a logarithm and the measurement delivers one, and the reason it delivers one is that each merge in a balanced merge tree costs about $n$ comparisons and there are about $\log_2 r$ levels of them.

But that is the worst a merge can cost, and a merge only reaches it when the two runs interleave element for element. Real natural runs do not, in general. A run that happens to lie entirely above its neighbour merges in a handful of comparisons. So the same $r$ can cost anywhere from $O(\log n)$ to $n-1$ comparisons per merge depending on how the runs’ values relate, and $r$ alone does not determine the cost — it bounds it.

That is a limit on the second parameter and it is the same limit the first parameter has always had here: $n$ does not determine an algorithm’s cost either, it bounds it, and everything on this site that fits a class to counts is fitting the behaviour of one family of inputs. The sweep above uses a construction that makes every merge as expensive as it can be, which makes the fitted curve the upper edge of a band rather than a line through the middle of one. Any figure quoting it says which.

Constructing the input turned out to be the hard part #

The first version of withRuns was wrong in a way worth recording, because it produced a figure that looked entirely reasonable.

It gave each run its own block of the value range: run 0 took the highest values, run 1 the next highest, and so on. Every run ascends, every boundary is a descent, and runsOf counts exactly $r$ of them. By every check available it was the right input.

Measured, Timsort’s cost barely moved between $r = 1$ and $r = 2$: 8,191 comparisons against 8,222. At $r = 6$ it was 8,358. The curve was almost flat where the bound says it should be climbing steeply, and $n + n \log r$ missed by 147%.

The cause is that runs which do not overlap in value are not runs, for merging purposes. Merging two runs where every element of one is smaller than every element of the other takes one comparison to discover that, and then galloping sweeps the whole of the smaller run across in $O(\log n)$ comparisons. The construction had accidentally built the easiest possible merge and repeated it.

The fix is to deal the sorted values round-robin into $r$ runs, so every run spans the whole value range and the merges genuinely interleave — which is what the natural runs of a shuffled array actually look like. That is the version above, and the comment in lib/practice.js records the failure rather than only the fix.

The general form of the mistake is one this site keeps meeting: an input built to have a property, which has the property, and which also has an unintended second property that decides the measurement. The randomness phase found the same shape when treap priorities were drawn from the key stream. Neither was caught by a correctness check, because neither produced a wrong answer — only a wrong picture.

Where the input stops mattering #

The most interesting thing in the sweep is not the fit. It is the point where the fit stops.

Timsort does not merge the runs it finds. It merges the runs it finds after extending every one shorter than minrun, and minrun is between 32 and 64. At n = 8,192 it is 32. So an input containing 8,192 runs of one element each is merged as though it contained 256 runs of thirty-two, because the first thing that happens to each one-element run is that it is binary-inserted into a group of thirty-two.

Past $r = n/\text{minrun}$, the input’s run structure stops being the algorithm’s second parameter. The measured cost at $r = 431$ and $r = 1{,}024$ is 60,986 and 52,646 comparisons — not rising, and not tracking $n + n \log r$, which predicts 79,885 and 90,112.

This is a ceiling that no statement of Timsort’s bound mentions, and it is not a small one: it says that for any input with more than a few hundred runs at this size, Timsort is a plain bottom-up merge sort over blocks of thirty-two and the adaptivity is gone. Which is fine — that is what minrun is for, and the alternative is merging thousands of tiny runs, which is worse — but it means the bound $O(n + n \log r)$ is describing behaviour in a region, and the region has an edge at a place decided by a constant.

That constant is the subject of the threshold somebody chose, and the ceiling above is the first of several places where the answer to “why is this algorithm fast” turns out to be “because of a number somebody picked in 2002”.

The ceiling is a condition on the mean run length, and the named inputs fail it #

The ceiling is stated above as $r = n/\text{minrun}$, which reads as a size-dependent limit. Divide through and it is not:

$$\frac{n}{r} \;>\; \text{minrun}.$$

Timsort is in its adaptive region exactly while the mean run length exceeds minrun, which is between 32 and 64 whatever $n$ is. That is a far more useful statement of the ceiling, because the left-hand side is a property of the input that a single scan reports and the right-hand side is a constant somebody chose in 2002.

Now check the inputs this collection has been using.

A uniformly random permutation has about $2n/3$ runs, so a mean run of 1.5 — outside the region by a factor of twenty. And nearlySorted has 42 runs at $n = 512$, a mean run of 12.2 — also outside it, by a factor of nearly three. Neither of the two inputs this site has made most of its adaptive claims on is in the region the bound describes.

That is not a contradiction and it explains the plate this section follows. Timsort’s fitted constant is 0.364 on nearly sorted input against 0.876 on random, a factor of 2.4, and both inputs have mean runs under minrun. So the adaptivity that shows up on nearly sorted input is not run adaptivity at all.

It comes from the other measure. Below the ceiling every run shorter than minrun is extended by binary insertion into a block of thirty-two, and a binary insertion sort’s cost is in the inversions inside its block. Nearly sorted input has 79 inversions at $n = 512$ against random input’s 62,873, so the extension phase is nearly free on one and full price on the other, while the merge phase — 256 blocks of thirty-two, merged bottom-up — is identical on both.

Which resolves the two measures the top of this essay separates into two phases of one algorithm:

Inversions govern the extension, which is what happens below the ceiling and is where every adaptive gain this site has measured on its named inputs comes from. Runs govern the merges, which is what the published bound is about and requires a mean run above minrun to reach.

An input with 181 runs at $n = 8{,}192$ — a mean run of 45 — is in the second region and tracks $n + n\log_2 r$; an input with 1,024 runs is in the first and does not. The sweep at the head of this essay crosses between them, and the crossing is where the algorithm stops being the one the bound describes.

Two consequences. A bound quoted in $r$ is describing a regime most real inputs are not in, since a mean run of thirty-two is a strong condition — it says the data arrives in sorted stretches of at least a page. And the constant that decides which regime holds is the same one the threshold somebody chose is about, doing something rather larger than trading a merge against an insertion: it is deciding which of two measures of presortedness the algorithm responds to. When galloping pays is the third mechanism, and it sits inside the merge phase where neither of these two measures reaches it.

The other three do not have this axis #

Timsort is the only one of the four library sorts whose bound mentions the input’s shape, and it is worth confirming that the other three genuinely lack the property rather than merely not advertising it.

All four fit $n \log n$ on nearly sorted input, Timsort included. That is not a failure of the audit; it is the audit doing what it is for. A complexity class is a statement about growth in $n$, and adaptivity lives in the constant — which is the site’s oldest theme, the constant the notation drops, reappearing with a specific and measurable identity. Timsort’s fitted constant over n = 256–16,384 is 0.364 on nearly sorted input and 0.876 on random input, a factor of 2.4, and the class is $n \log n$ both times.

So the second parameter is not visible in the class at all. It is visible in the constant, and the only way to see it is to hold $n$ fixed and sweep the input — which is what the figure at the top of this essay does, and what nothing on this site could do before this phase.

What this changes about everything already written #

Nine fields of essays have used the five input kinds as though they were a sample of the space of inputs. They are not; they are five points, chosen for what they demonstrate, and four of the five sit in corners.

That is defensible for the purpose they were chosen for — a corner is exactly where an algorithm’s worst behaviour lives, and finding worst behaviour is what a lower-bound argument needs. It is not defensible as a claim about typical inputs, and no essay here has made one. But the vocabulary invited it: five names, one of which is “random”, reads like a survey.

The honest description of what this site has been measuring is: ten algorithms at five chosen points of a two-dimensional space, with the second dimension unmeasured until now. Adding the measurement does not invalidate any of it. It does put a name on what was missing, and it makes one specific thing possible that was not — asking how an algorithm behaves between the points, which is where every real input actually lives.

The remaining essays in this field use the new axis where it is the subject and the old five where it is not, and each figure says which. The five names are not going away; they are a good spanning set for the corners, and a corner is still where the interesting failures are. What has changed is that there is now a way to say how far from one a given input sits.

The run sweep, three more ways #

The run count is the axis this whole essay is about, so the sweep is taken again at another size, over a wider range, and with the quadratic algorithm left out.

A third size between the two settles that the shape is a shape rather than two readings, and it is worth taking the axis as far as it goes there too — past the minrun ceiling, where a “run” stops being a run the input supplied and becomes one the algorithm manufactured.

And the two linearithmic sorts alone are worth one plate, because the gap between them is the whole of what run detection buys and a quadratic line sets a scale that hides it.

What the five input kinds actually were #

With the plane drawn, the five named input kinds can finally be located rather than described.

• sorted — 1 run, 0 inversions. The corner.
• reversed — 1 run, the maximum inversions. The other corner, and the one that shows why runs and inversions cannot be collapsed into a single number: reversed input is the easiest possible input for Timsort and the hardest possible for insertion sort, and it sits at an extreme of both axes.
• nearly sorted — at n = 512, 42 runs and 79 inversions. Close to the sorted corner on both axes, which is why every adaptive algorithm looks good on it, and a long way from either extreme on both.
• few distinct values — 209 runs and 54,617 inversions, against random input’s 211 and 62,873. Not “nearly” anything: eight distinct values repeated has almost exactly the shape of random data by both measures, and the algorithms nonetheless behave completely differently on the two.
• random — 211 runs at n = 512, which is close to the expected $(2n-1)/3 \approx 341$ for a uniformly random permutation, allowing for the seed and for equal values.

Two of those five are single runs and they are opposite extremes of the other measure. A figure that drew only the run count would show them as identical inputs. They are not.

That last figure is the reason the axis matters. Insertion sort takes 9,352 comparisons on this input against Timsort’s 33,449, and insertion sort takes 16,881,018 on random input of the same size. An algorithm that is best on a measured region and catastrophic outside it is exactly what an adaptive library sort is trying to approximate without the catastrophe — and the region is now a region rather than an adjective.