Quicksort: Lomuto vs Hoare vs Bentley-McIlroy 3-Way Partitioning

Anatomy of the Three Partition Schemes

Given a subarray $A[lo \dots hi]$ and a chosen pivot value $v$, partitioning rearranges elements in-place so keys smaller than $v$ precede keys larger than $v$. Yet the choice of pointer invariant changes swap counts, branch predictability, and duplicate-key behavior dramatically:

Entropy-Optimal Sorting & Pivot Selection

Suppose an array of $n$ elements has $k$ distinct values occurring with frequencies $f_1, f_2, \dots, f_k$ and empirical probabilities $p_i = f_i / n$. The Shannon entropy of the multiset is $H = -\sum_{i=1}^k p_i \log_2 p_i \le \log_2 k$. Sedgewick and Bentley proved that 3-way Quicksort uses $O(n H + n)$ comparisons—matching the information-theoretic lower bound $\log_2\!\left(\frac{n!}{f_1! f_2! \cdots f_k!}\right) = n H - O(k \log n)$ up to a constant factor!

To prevent adversarial inputs (sorted, reverse-sorted, or "organ-pipe" arrays) from picking extreme pivots, production implementations use:

• Median-of-Three ($n \le 128$): Median of $(A[lo], A[mid], A[hi])$, which also places sentinels at the ends.
• Tukey's Ninther ($n > 128$): Median of three medians of three ($9$ samples), costing only $12$ comparisons while concentrating the pivot tightly around the true median and defeating killer inputs like McIlroy's "AntiQsort" adversary when combined with pattern randomization.

Production C++20 Implementation: Hoare, 3-Way & Tail-Call Bounded Quicksort

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

// Median-of-3 pivot selection that also sorts A[lo] <= A[mid] <= A[hi] as sentinels
template <std::totally_ordered T>
void sort_median_of_three(T* a, std::size_t lo, std::size_t mid, std::size_t hi) noexcept {
    if (a[mid] < a[lo]) std::swap(a[lo], a[mid]);
    if (a[hi]  < a[lo]) std::swap(a[lo], a[hi]);
    if (a[hi]  < a[mid]) std::swap(a[mid], a[hi]);
}

// Hoare 2-Way Partition: stops on keys == pivot to prevent O(N^2) on equal elements
template <std::totally_ordered T>
std::size_t hoare_partition(T* a, std::size_t lo, std::size_t hi) noexcept {
    const std::size_t mid = lo + (hi - lo) / 2;
    sort_median_of_three(a, lo, mid, hi);
    T pivot = a[mid];
    std::size_t i = lo;
    std::size_t j = hi;
    while (true) {
        while (a[i] < pivot) ++i;
        while (pivot < a[j]) --j;
        if (i >= j) return j;
        std::swap(a[i], a[j]);
        ++i;
        --j;
    }
}

// Dijkstra 3-Way Partition + Sedgewick Tail-Call Elimination (Guarantees O(log N) stack depth)
template <std::totally_ordered T>
void quicksort_3way(T* a, std::size_t lo, std::size_t hi) noexcept {
    while (lo < hi) {
        const std::size_t mid = lo + (hi - lo) / 2;
        sort_median_of_three(a, lo, mid, hi);
        const T pivot = a[mid];

        // Invariant: a[lo..lt-1] < pivot, a[lt..i-1] == pivot, a[gt+1..hi] > pivot
        std::size_t lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (a[i] < pivot) {
                std::swap(a[lt++], a[i++]);
            } else if (pivot < a[i]) {
                std::swap(a[i], a[gt--]);
            } else {
                ++i;
            }
        }

        // Tail-Call Elimination: recurse ONLY on the smaller partition (<= N/2),
        // and iterate the while-loop on the larger partition!
        const std::size_t left_len  = (lt > lo) ? (lt - lo) : 0;
        const std::size_t right_len = (hi > gt) ? (hi - gt) : 0;

        if (left_len < right_len) {
            if (lt > lo + 1) quicksort_3way(a, lo, lt - 1);
            lo = gt + 1;
        } else {
            if (hi > gt + 1) quicksort_3way(a, gt + 1, hi);
            if (lt == 0) break; // Prevent unsigned underflow when lt == 0
            hi = lt - 1;
        }
    }
}