When galloping pays

A merge takes the smaller of two heads, writes it out, and repeats. That is the whole algorithm, it costs one comparison per element written, and it is optimal in the sense that a merge of two runs of length $m$ and $n$ can require $m + n - 1$ comparisons in the worst case and no fewer.

The worst case is when the two runs interleave perfectly. Most real merges are not that. If one run’s next thousand elements all belong before the other run’s next element, the element-at-a-time merge will discover this a thousand times, one comparison each. Something that could establish it in ten comparisons is available: search, rather than scan.

Timsort’s name for that is galloping, and the interesting part is not the search. It is the decision about when to use it.

The search, in the form Timsort uses #

Given a sorted run and a key, find where the key belongs. Binary search does it in $\lceil \log_2 k \rceil$ comparisons for a run of length $k$, and that is the wrong tool here: the answer is usually near the start of the run, because the merge has just been taking elements one at a time from the other side, and a binary search would spend its first comparison in the middle of a run when the answer is three positions in.

So Timsort uses an exponential search — probe at offsets 1, 3, 7, 15, 31 until the answer is bracketed, then binary search inside the bracket. Finding an answer at position $d$ costs $2\log_2 d$ comparisons rather than $\log_2 k$, and when $d$ is small that is much better, and when $d$ is large it is barely worse.

The asymmetry matters. Galloping is used exactly when one side has been winning, which means the next answer is expected to be far along that run — so the search wants to be cheap when the answer is close and it also wants to handle the case where the answer is very far. The doubling probe is the standard answer to both at once and it is the same shape as the doubling in choosing a growth factor: geometric probing gives a logarithmic number of steps with an amortised constant that does not depend on knowing the answer’s size in advance.

What the mode costs when it does not help #

The number worth the whole essay is in the third row of the figure above.

On random input at n = 8,192, Timsort with galloping enabled does 95,772 comparisons. With the mode removed entirely it does 95,766.

Six comparisons. Over 8,192 elements, 255 merges, and 134,256 branches, the entire cost of carrying a mechanism that does nothing on this input is six comparisons.

That is not luck. It is what the mode’s entry condition buys. Galloping is entered only after one side has won MIN_GALLOP — seven — times in a row, which on interleaved random data essentially never happens; the probability of seven consecutive wins by one side is about $2 \times 2^{-7}$, and each occurrence costs a handful of comparisons to discover it was a false alarm before the merge drops back. Across a whole sort of random data, galloping fired in 4 of 255 merges and moved 8 elements.

Compare that with what happens where the structure is there:

A mode that saves 40% where it applies and costs 0.006% where it does not is a mode that can be left switched on, and that is the design principle rather than an observation about these particular inputs. Every adaptive mechanism in a library is built to this shape, because a library cannot know its caller’s data and so cannot afford a mechanism whose bad case is expensive.

The few-distinct-values row is the one that would not have been predicted from the run map. That input has 209 natural runs at n = 512 against random’s 211 — by the run measure the two inputs are nearly identical, and a run is a property of the input showed they sit almost on top of each other in the presortedness plane. Galloping saves 36% on one and nothing on the other.

The reason is that galloping is not about runs. It is about stretches of equal or near-equal values, which is what a merge sees as “one side winning repeatedly”. With eight distinct values in 8,192 elements, every merge contains long stretches where one side’s value is the same and the tie-break sends them all to the same side. Neither of the two disorder measures sees that. It is a third property of the input, it decides a third of the comparison count, and nothing in the vocabulary has a name for it.

MIN_GALLOP, swept #

Seven is a number in CPython’s listobject.c. It has been seven since 2002. What does it buy?

The measurement says something slightly awkward: on comparisons, the best value is 1. Entering galloping as soon as one side wins a single comparison costs 33,246 on nearly sorted input against the shipped seven’s 33,449, and 58,505 against 58,599 on few distinct values. Never worse, occasionally 0.6% better.

The site’s habit at this point is not to declare the library wrong. It is to ask what counter the choice was made against, because a constant that looks badly chosen for one quantity is usually well chosen for another.

Galloping’s cost is not principally in comparisons. It is in the branches and the pointer arithmetic per attempt: entering the mode, running two searches, checking whether either paid, and adjusting minGallop — a fixed overhead per attempt that this site’s counters do not charge for, and one that a real merge pays in instructions. MIN_GALLOP = 1 on random data would attempt a gallop on almost every element written, and each attempt would fail, and the comparison count would barely move while the instruction count doubled.

This site cannot measure that. It can measure that the comparison count does not justify the value 7, and it can say precisely what the missing quantity is. Both of those are more useful than a confident conclusion in either direction, and the count somebody chose is the essay that argues why.

The adjustment nobody mentions #

There is a further mechanism, and it is the part most descriptions of Timsort omit.

minGallop is not a constant during a sort. It starts at 7. Every time a gallop pays — returns at least minGallop elements — it is decreased by one, to a floor of 1. Every time a merge leaves galloping mode it is increased by two.

So the threshold adapts to the data as the sort proceeds. A sort of input that galloping suits drives minGallop down towards 1 within the first few merges and then behaves like the aggressive setting for the rest of the run. A sort of random data pushes it up, and after a few failed attempts the mode is effectively disabled for the remainder.

That is why the shipped 7 costs only 0.6% more than the measured optimum of 1: on the input where 1 would be better, the algorithm arrives at something close to 1 by itself within a few merges. The constant is an initial condition rather than a setting, and a sweep that holds it fixed — like the one above — is measuring a version of the algorithm that does not exist.

That is a real limitation of the sweep and it is stated on the figure. It is also the strongest possible illustration of this field’s thesis: the constant is not a parameter of the algorithm, it is part of the algorithm, entangled with a feedback loop that changes it. Asking “what is the best MIN_GALLOP” is already the wrong question, and it took a figure that answers it to see that.

Where the comparisons actually go #

One more measurement, because it locates galloping’s saving precisely rather than in aggregate.

On nearly sorted input, 79 of the 224 merges entered galloping mode at least once, and 22,939 elements were moved by jumps rather than by individual comparisons. The saving is 22,104 comparisons, so each galloped element saved slightly under one comparison — which is the expected figure, since the alternative was one comparison per element and the gallops themselves cost something.

That ratio is the honest ceiling on what galloping can ever save: at most one comparison per element, and only for elements that a jump can cover. It cannot make a merge cheaper than the number of elements that genuinely interleave. Timsort on nearly sorted input costs 33,449 comparisons for 8,192 elements, or about four comparisons per element, and that is the merge tree’s depth rather than anything galloping controls.

Which is the same point the run sweep made from the other side. Galloping reduces the cost of each merge; it does not reduce the number of merges. The number of merges is decided by minrun and the merge policy, and those are the subject of the threshold somebody chose and the invariant that was wrong for seven years.

Two searches, and why they are not the same search #

There are two gallop functions in every Timsort, and the difference between them is one comparison operator. gallopLeft finds the first position where an element is not less than the key; gallopRight finds the first position where an element is greater than the key. On a run with no repeated values they return the same answer. On a run with repeated values they differ by however many copies there are.

That difference is the stability guarantee.

A merge is stable if, when two elements compare equal, the one from the earlier run is written first. In the element-at-a-time loop that is enforced by a single < rather than <=. In galloping mode it has to be enforced twice, in opposite directions: the search over the left run must include elements equal to the key (so they go out first) and the search over the right run must exclude them (so they wait). Get either backwards and the merge still produces a sorted array, of the correct length, containing the correct elements — and equal elements in the wrong order.

Nothing this site measures would notice. The comparison count is the same to within a handful, the output passes every sortedness check, and stability is not a property of a sorted array of numbers at all: two equal integers are indistinguishable, so the defect is invisible in the very data this site sorts. It is only visible when the elements carry something other than their sort key, which is exactly the case Java’s Collections.sort exists for.

That is a genuine limit on what is measurable here and it is worth stating plainly rather than working around. This site sorts numbers, so this site cannot test stability. What it can do is name the two functions, say which direction each settles ties in, and record that the guarantee lives in a pair of comparison operators one line apart in two functions — the same shape as the strict/non-strict asymmetry in the run detection, and for the same reason.

The mode’s own dial, four ways #

Galloping is a mode with a threshold in it, and both the threshold and the size are worth turning before any number about it is quoted.

Fifteen is the other end of the same dial, and the reason to draw both is that the three inputs do not agree about which end they want.

Neither of those changes the size, and the mode’s benefit is a benefit per merge rather than per element — so how many merges there are decides how much of it there is to have. A quarter of the array is roughly two fewer levels of merging, which is where the next plate comes from.

What galloping costs on the fifth counter #

There is one more quantity this phase can put beside the comparison count, and galloping does not come out of it as well.

On few distinct values Timsort does 58,599 comparisons and mispredicts 27,937 times; introsort does 243,350 comparisons and mispredicts 9,116 times. Four times the comparisons and a third of the mispredictions. The two counters not only disagree about the ranking, they disagree by a factor of twelve in the ratio.

That is the branch the machine guesses’s territory rather than this essay’s, and the reason it appears here is that galloping is one of the things responsible. Every gallop is an exponential probe followed by a binary search, and a binary search’s comparison is close to unpredictable by construction — it is designed to halve the remaining possibilities, which is another way of saying it is designed to be a coin flip. Replacing a thousand predictable comparisons with ten unpredictable ones is not obviously a gain, and whether it is depends on numbers no counter here reports.

The property nobody named is the one the algorithm measures #

The essay’s sharpest observation is that galloping responds to something neither disorder measure captures — the two inputs with 209 and 211 runs behave completely differently — and that nothing in the vocabulary has a name for it. There is a name available, and the algorithm is already computing it.

The property is the length of the stretches over which one side of a merge wins consecutively. That is exactly what a merge experiences, exactly what makes a jump worth taking, and exactly what minGallop is a threshold on. Few distinct values produces long win-runs because a stretch of equal keys all go the same way under a stable tie-break; random data produces win-runs whose lengths are geometric with mean two, which is why seven consecutive wins essentially never happens there.

So the missing third coordinate of the presortedness plane is the distribution of win-run lengths, and it is not an exotic statistic that would have to be invented — it is a histogram of a quantity the merge loop already computes and then throws away.

Two things follow and both are cheap.

It is measurable without changing the algorithm. Record the length of each win-run as the merge sees it, and the resulting distribution is a description of the input at exactly the grain galloping cares about. On few distinct values it would have a long tail; on random data it would be geometric with mean two; on nearly sorted data it would be dominated by one enormous run per merge. Three inputs, three distinguishable shapes, where the run count gives two of them the same number.

And the algorithm’s own adaptation is a one-bit summary of it. minGallop walks down when win-runs are long and up when they are short, so its trajectory during a sort is a running estimate of the same statistic, coarsened to a single integer. The threshold is not merely a parameter that responds to the data; it is the algorithm’s measurement of the property that decides its cost, and reading it out would give the third coordinate for free.

That reframes the sweep in this essay one last time. Holding minGallop fixed does not merely measure a version of the algorithm that does not exist — it measures a version with its instrument disconnected, which is why the fixed-threshold optimum is 1 and the adaptive version’s initial value barely matters.

The instrument had to be fixed to measure this #

A closing note about the implementation, because it caught a real defect and the defect is the kind that produces beautiful wrong figures.

Timsort’s merge copies the shorter run into scratch memory and merges back into place. So half of every gallop searches the scratch buffer, which is a plain array outside the counted structure — and in the first version of lib/practice.js those comparisons were not counted at all. Galloping looked better than it is by exactly the comparisons it spends.

The fix is three characters: charge them to the counted array explicitly. The reads are deliberately not charged, because scratch is the algorithm’s own memory and alloc has already accounted for holding it.

The reason it is worth recording is that the sortedness check would never have caught it, the fit would never have caught it, and the resulting figure would have shown galloping saving rather more than 40% with no sign that anything was wrong. A counter that is not consulted is indistinguishable from a cost that does not exist, and the only defence is looking at where the algorithm’s memory actually is.