Top-Down vs Bottom-Up Merge Sort & Counting Inversions in O(N log N)

The Two-Finger Merge & Recursion Tree Analysis

John von Neumann (1945) designed Merge Sort around a simple linear-time primitive: merging two already-sorted halves $A[lo \dots mid]$ and $A[mid+1 \dots hi]$ into a single sorted range of length $n = hi - lo + 1$. Each step compares the front elements of both halves and advances the pointer of the smaller element, taking at most $n - 1$ comparisons and exactly $n$ element moves.

The recurrence $T(n) = 2T(n/2) + \Theta(n)$ expands into a binary recursion tree of depth $\lceil \log_2 n \rceil$. At level $d \in [0, \log_2 n]$, there are $2^d$ subproblems each of size $n / 2^d$, so the total merge work at every level is $2^d \cdot c(n/2^d) = cn$. Summing across all $\log_2 n$ levels yields worst-case, average-case, and best-case $\Theta(n \log n)$ time, with at most $n \lceil \log_2 n \rceil - 2^{\lceil \log_2 n \rceil} + 1$ key comparisons.

Top-Down vs. Bottom-Up & Ping-Pong Buffer Optimization

Naive Merge Sort implementations allocate a fresh std::vector<T> temp inside every call to merge(), turning a fast memory-bound sort into a malloc/free allocator bottleneck. Production implementations combine three structural optimizations:

1. Single Pre-Allocated Scratch Buffer: Allocate one auxiliary buffer aux of size $n$ (or $n/2$) at the top level and pass pointers down.
2. Ping-Pong Role Reversal (Zero Copy-Back): Instead of copying merged elements into aux and immediately copying them back into a on every level (which doubles memory bandwidth to $2n \log_2 n$ writes), alternate the source and destination roles between a and aux at each recursion depth, cutting total element moves in half to $n \log_2 n$.
3. Already-Sorted Skip Check: Before merging $A[lo \dots mid]$ and $A[mid+1 \dots hi]$, check if $A[mid] \le A[mid+1]$. If true, the two halves are already globally ordered and the merge step can be skipped in $O(1)$ time—making Merge Sort run in $O(n)$ time on sorted inputs!
4. Bottom-Up Iterative Merge Sort: Eliminates recursion stack frames entirely by sweeping width $w = 1, 2, 4, 8, \dots$ across the array. It is the canonical choice for sorting linked lists in $O(1)$ auxiliary space.

Production C++20 Implementation: Ping-Pong Bottom-Up Merge Sort & Inversion Counter

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <vector>

// 1. Exact Inversion Counter in O(N log N) time using a single pre-allocated buffer
template <std::totally_ordered T>
std::uint64_t count_inversions_rec(T* a, T* aux, std::size_t lo, std::size_t hi) noexcept {
    if (hi - lo <= 1) return 0; // Half-open interval [lo, hi)
    const std::size_t mid = lo + (hi - lo) / 2;

    std::uint64_t inv = 0;
    inv += count_inversions_rec(a, aux, lo, mid);
    inv += count_inversions_rec(a, aux, mid, hi);

    // Optimization: if already ordered across boundary, 0 split inversions!
    if (!(a[mid] < a[mid - 1])) return inv;

    std::size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (!(a[j] < a[i])) { // a[i] <= a[j]: preserves stability!
            aux[k++] = std::move(a[i++]);
        } else {
            aux[k++] = std::move(a[j++]);
            inv += (mid - i); // All remaining elements in [i, mid) are > a[j]
        }
    }
    while (i < mid) aux[k++] = std::move(a[i++]);
    while (j < hi)  aux[k++] = std::move(a[j++]);
    std::move(aux + lo, aux + hi, a + lo);
    return inv;
}

template <std::totally_ordered T>
std::uint64_t count_inversions(std::vector<T> a) {
    if (a.size() <= 1) return 0;
    std::vector<T> aux(a.size());
    return count_inversions_rec(a.data(), aux.data(), 0, a.size());
}

// 2. Ping-Pong Bottom-Up Merge Sort (Zero Copy-Back Overhead)
template <std::totally_ordered T>
void mergesort_bottom_up_pingpong(std::vector<T>& a) {
    const std::size_t n = a.size();
    if (n <= 1) return;

    std::vector<T> aux(n);
    T* src = a.data();
    T* dst = aux.data();

    for (std::size_t width = 1; width < n; width <<= 1) {
        for (std::size_t lo = 0; lo < n; lo += (width << 1)) {
            const std::size_t mid = std::min(lo + width, n);
            const std::size_t hi  = std::min(lo + (width << 1), n);
            std::size_t i = lo, j = mid, k = lo;
            while (i < mid && j < hi) {
                if (!(src[j] < src[i])) dst[k++] = std::move(src[i++]);
                else                    dst[k++] = std::move(src[j++]);
            }
            while (i < mid) dst[k++] = std::move(src[i++]);
            while (j < hi)  dst[k++] = std::move(src[j++]);
        }
        std::swap(src, dst); // Ping-pong buffers for next width pass!
    }
    if (src != a.data()) {
        std::move(src, src + n, a.data());
    }
}