Concept

MIN_GALLOP — where it appears

The number of consecutive wins after which a merge switches to exponential search, and back again when the search stops paying. It moves during a run in response to whether the search is paying, which makes it a policy rather than a constant despite being one integer.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

When galloping pays

Timsort's merge does not always take elements one at a time. When one run has won seven times in a row it switches to searching for how many to take at once, and switches back when that stops paying. The mode saves 22,104 comparisons on nearly sorted input, 33,270 on input with few distinct values, and costs exactly six on random input — which is the whole design in three numbers.

practice · Practice

The threshold somebody chose

A minrun of 32. An insertion cutoff of 16. A gallop threshold of 7. A depth limit of twice the logarithm. Four numbers, in four real source files, none of which appears in any complexity analysis — and each of which decides more about what these algorithms do than the analysis does. Swept, they turn out not to be optima, and finding out what they are instead is the point.

practice · Count

Named alongside it

The objects these essays reach for when they reach for this one.

Comparison count Galloping Introsort Timsort Adaptive sort Binary search Cutoff Depth limit Exponential search Insertion cutoff Merge policy minrun

All concepts