Galloping Merge

Galloping merge is an optimized merge procedure used in adaptive merge sorts such as Timsort. It starts like ordinary merging, but when one run wins many comparisons in a row, it switches to exponential search to copy a larger block at once.

You use it when merging two sorted runs where one run often contains a long streak of smaller elements.

Problem

Given two sorted runs ( L ) and ( R ), merge them into one sorted output while reducing comparison cost when the merge is uneven.

Idea

Ordinary merge compares one pair at a time:

if L[i] <= R[j]:
    output.append(L[i])
    i = i + 1
else:
    output.append(R[j])
    j = j + 1

Galloping merge watches how often one side wins. If one run wins repeatedly, it uses exponential search to find how many elements from that run can be copied before the next element from the other run.

Algorithm

galloping_merge(L, R, min_gallop):
    i = 0
    j = 0
    output = []

    wins_left = 0
    wins_right = 0

    while i < length(L) and j < length(R):
        if L[i] <= R[j]:
            output.append(L[i])
            i = i + 1
            wins_left = wins_left + 1
            wins_right = 0
        else:
            output.append(R[j])
            j = j + 1
            wins_right = wins_right + 1
            wins_left = 0

        if wins_left >= min_gallop:
            p = gallop_left(L, i, R[j])
            output.extend(L[i:p])
            i = p
            wins_left = 0

        if wins_right >= min_gallop:
            p = gallop_left(R, j, L[i])
            output.extend(R[j:p])
            j = p
            wins_right = 0

    output.extend(L[i:])
    output.extend(R[j:])
    return output

Gallop Search

Gallop search is exponential search followed by binary search inside the discovered range.

gallop_left(A, start, x):
    step = 1

    while start + step < length(A) and A[start + step] <= x:
        step = step * 2

    lo = start
    hi = min(start + step, length(A))

    return upper_bound(A, lo, hi, x)

Example

Merge:

[ L = [1, 2, 3, 4, 5, 6] ]

[ R = [100, 101, 102] ]

Ordinary merge compares repeatedly and copies one item at a time from ( L ). Galloping merge detects that ( L ) keeps winning, then copies the whole prefix of ( L ) in one block.

Output:

[ [1, 2, 3, 4, 5, 6, 100, 101, 102] ]

Correctness

Galloping merge preserves the ordinary merge invariant: the output is sorted and contains the smallest unmerged elements from both runs.

When galloping copies a block from one run, exponential and binary search locate the maximal prefix whose elements can appear before the current element of the other run. Copying that prefix is equivalent to repeated ordinary merge steps, so sorted order is preserved.

Complexity

Space:

[ O(n) ]

for the merge output buffer.

Stability

Galloping merge is stable if equal elements from the left run are emitted before equal elements from the right run. This requires using an upper-bound style search when copying from the left.

When to Use

Galloping merge is useful when:

• merging natural runs
• one run often wins many comparisons
• data has clustered or partially ordered structure
• adaptive sorting performance matters

It is one of the main low-level optimizations that makes Timsort efficient on real-world inputs.