Production Case Study: Python/V8 TimSort (Galloping & Run Invariants) vs Rust pdqsort

Part I: TimSort (Tim Peters, 2002) — Adaptive Stable Merging

Designed by Tim Peters in 2002 for CPython (and subsequently adopted by Java Arrays.sort(Object[]), Android, and V8's Array.prototype.sort), TimSort is a natural adaptive Merge Sort built around four hardware-tuned mechanisms:

1. Natural Run Detection & Reverse-Run Inversion: A linear scan identifies the longest prefix starting at index $i$ that is either non-decreasing ($A[0] \le A[1] \le \dots$) or strictly decreasing ($A[0] > A[1] > \dots$). Why strictly decreasing? Reversing a non-strictly decreasing run ($A[0] \ge A[1]$) in place would flip equal keys and violate stability!
2. Minimum Run Length (minrun $\in [32, 64]$): If a natural run is shorter than minrun, TimSort extends it to length minrun using Binary Insertion Sort. Furthermore, minrun is chosen so that $N / \text{minrun}$ is a power of $2$ (or slightly less than a power of $2$), ensuring the final top-level merges are perfectly balanced!
3. The Run Stack Balance Invariants: Active runs are pushed onto a stack. To ensure merges happen between runs of comparable size while bounding stack depth by $O(\log N)$, TimSort maintains two invariants on the top three run lengths $X, Y, Z$ (where $Z$ is on top of the stack): $$X > Y + Z \quad \text{and} \quad Y > Z$$ Notice this is the exact recurrence of the Fibonacci numbers! If either invariant is violated, $Y$ is merged with $\min(X, Z)$.
4. Galloping Mode (MIN_GALLOP = 7): During a two-finger merge of runs $A$ and $B$, if one run wins $7$ times in a row, TimSort switches from $1$-by-$1$ linear comparison to Galloping (Exponential + Binary Search): it probes offsets $1, 3, 7, 15, 2^k - 1$ to find the entire contiguous chunk of $A$ smaller than $B[j]$ in $O(\log m)$ comparisons and copies the whole chunk via a single vectorized memmove!

Part II: Pattern-Defeating Quicksort (pdqsort, Orson Peters 2021)

When stability is not required (sorting primitive slices in Rust's slice::sort_unstable or Go 1.19+'s slices.Sort), allocating $O(N)$ merge space is undesirable. Orson Peters's pdqsort upgrades Musser's Introsort into an adaptive, branchless $O(1)$-auxiliary-space engine:

• Adaptive $O(N)$ Fast Paths on Pre-Sorted / Equal Data: When a partition moves zero elements (meaning no keys crossed the pivot), the subarray might already be sorted! pdqsort runs a bounded speculative Insertion Sort (partial_insertion_sort allowing up to 8 misplaced elements)—finishing in $O(N)$ time on sorted and nearly-sorted arrays.
• 3-Way Left-Partitioning on Duplicates: If the chosen pivot equals the predecessor element from the parent partition ($v == A[lo - 1]$), all keys strictly less than $v$ were already partitioned to the left. A single PartitionEqual pass packs all keys equal to $v$ and skips them!
• Branchless BlockQuicksort + Pattern Busting: Uses 64-element offset blocks to avoid branch mispredictions when types have branchless comparators, and deterministically shuffles endpoint elements when a highly unbalanced split ($< N/8$) occurs before falling back to Heapsort after $\log_2 N$ bad splits.

Production C++20 Implementation: Galloping Search (gallop_left / gallop_right) & Speculative Insertion

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <utility>

// TimSort's gallop_right: Exponential + Binary search for the first index k in a[0..n-1]
// where key < a[k] (so all elements in a[0..k-1] are <= key, preserving stability).
template <std::totally_ordered T>
std::size_t gallop_right(const T& key, const T* a, std::size_t n, std::size_t hint = 0) noexcept {
    std::size_t last_ofs = 0;
    std::size_t ofs = 1;

    if (key < a[hint]) {
        // Gallop left from hint
        const std::size_t max_ofs = hint + 1;
        while (ofs < max_ofs && key < a[hint - ofs]) {
            last_ofs = ofs;
            ofs = (ofs << 1) + 1;
        }
        if (ofs > max_ofs) ofs = max_ofs;
        std::size_t tmp = last_ofs;
        last_ofs = hint - ofs;
        ofs = hint - tmp;
    } else {
        // Gallop right from hint: offsets 1, 3, 7, 15, ...
        const std::size_t max_ofs = n - hint;
        while (ofs < max_ofs && !(key < a[hint + ofs])) {
            last_ofs = ofs;
            ofs = (ofs << 1) + 1;
        }
        if (ofs > max_ofs) ofs = max_ofs;
        last_ofs += hint;
        ofs += hint;
    }

    // Standard half-open binary search inside the bracketed window (last_ofs, ofs]
    std::size_t lo = last_ofs;
    std::size_t hi = ofs;
    while (lo < hi) {
        const std::size_t mid = lo + ((hi - lo) >> 1);
        if (key < a[mid]) hi = mid;
        else              lo = mid + 1;
    }
    return lo;
}

// pdqsort's Speculative Partial Insertion Sort: sorts in O(N) if <= 8 elements are out of order,
// or aborts immediately in O(1) once 8 inversions are exceeded!
template <std::totally_ordered T>
bool partial_insertion_sort(T* first, T* last) noexcept {
    if (last - first <= 1) return true;
    constexpr int MAX_STEPS = 8;
    int steps = 0;

    for (T* cur = first + 1; cur != last; ++cur) {
        if (*cur < *(cur - 1)) {
            if (++steps > MAX_STEPS) return false; // Abort early: array is not nearly sorted
            T val = std::move(*cur);
            T* j = cur;
            do {
                *j = std::move(*(j - 1));
                --j;
            } while (j != first && val < *(j - 1));
            *j = std::move(val);
        }
    }
    return true;
}