What triggers galloping mode in a Timsort merge, and why does it lose on random data?

## The problem galloping solves Merging two ordered runs `A` and `B` with the textbook loop costs one comparison per element emitted. That is the information-theoretic price when the runs interleave evenly: to know which element comes next you genuinely have to ask. But real data is often not evenly interleaved. Consider merging a large accumulated run with a freshly-arrived run whose keys are all higher: the textbook loop spends one comparison for every one of the accumulated run's elements, each time re-learning the same fact — the other head is still bigger. Galloping replaces that linear discovery with an exponential one. When the merge notices that one side keeps winning, it stops asking element by element and instead searches ahead: is the loser's head beyond offset 1? beyond 2? 4? 8? 16? Once a bracket is found, a binary search inside it pins the exact boundary. The whole stretch of the winning run up to that boundary is then copied as one block. Finding a run of length `k` this way costs about `2 * log2(k)` comparisons instead of `k`. ## The trigger The merge maintains a counter of how many consecutive elements have come from the same run. When that counter reaches a threshold — conventionally named `min_gallop` and defaulting to 7 — the merge switches into galloping mode for both sides. It stays there while galloping keeps producing worthwhile blocks, and drops back to the one-at-a-time loop when a gallop returns a block shorter than the threshold, meaning the runs have started interleaving again. ## Why it is a loss on random data With two runs of uniformly random values, the next element is about equally likely to come from either side. The probability of one side winning seven times in a row is small but not negligible, so galloping is entered occasionally by chance. Once entered, the probe sequence costs comparisons that the plain loop would not have spent, and it finds a block of length one or two, because the winner is about to flip again. Every one of those attempts is pure overhead. This is why the mode is threshold-gated rather than always-on, and it is the honest answer to "is galloping strictly better?" — it is not. It is a bet that a streak predicts a longer streak, which holds on structured data and fails on random data. The threshold sets how much evidence is required before placing the bet, and the design accepts a small constant-factor penalty on random input in exchange for a large win on clustered input. Implementations reduce even that penalty by making the threshold adaptive. Roughly: when a merge leaves galloping mode without having profited, the threshold is nudged upward, making the next bet harder to trigger; while galloping keeps paying, the threshold is eased downward so the mode re-enters readily. On adversarial or purely random input the threshold drifts up and galloping effectively switches itself off; on data with long one-sided stretches it drifts down and stays engaged. ## The shapes where it pays enormously - **Concatenated ordered sources.** Merging two runs where nearly all of one precedes nearly all of the other: the merge finishes in O(log n) comparisons plus the block copies, instead of O(n) comparisons. - **Repeatedly appended batches.** A large sorted body merged with a small sorted tail whose keys are mostly higher — every merge round hits the one-sided pattern. - **Clustered duplicates.** Long stretches of equal keys on one side produce long winning streaks. ## Why it belongs in a library sort Galloping is what turns Timsort's merge phase from "good" into "asymptotically sensitive to the data's structure". Without it, run detection still gives you fewer merge rounds, but each round still costs a full `n` comparisons. With it, a round over highly one-sided runs costs closer to the logarithm of the block lengths. The combination — detect what is already ordered, then merge cheaply when the runs turn out to be one-sided — is why the sort collapses toward linear on structured input. ## What to say when asked Name the trigger (a streak of consecutive wins crossing a threshold), describe the mechanism (exponential probing, then a binary search, then a block copy), and be explicit that it is a bet that loses on random data — which is exactly why the threshold exists and why implementations adapt it.