Pattern-defeating quicksort (pdqsort)

Deep dive

How it works

In: a mutable slice and a strict weak order · Out: the slice sorted, equal keys in any order · State: none (O(log n) stack) · Cost: O(n log n) worst case, O(n) on sorted, reverse-sorted or few-distinct-key input

recurse(v, pred, limit) loops (tail-recursing on the larger side):

1. len ≤ 24 → insertion sort, return.
2. limit = 0 (too many bad partitions) → heapsort, return.
3. If the previous partition was unbalanced, swap a few elements to break patterns, decrement limit.
4. Pick pivot: median of 3 (len/4, len/2, 3len/4) or, if len > 128, a ninther (median of 3 medians). If the sampling needed no swaps, the slice is "likely sorted".
5. If likely sorted and the last partition was balanced and did no swaps, try partial insertion sort (give up after 8 moves); if it finishes, return.
6. If a predecessor pred exists (the previous pivot, left of this slice) and !(pred < pivot), then pivot == pred, everything here is ≥ pred, so partition into == pivot / > pivot and continue with the > part only. This is what makes many duplicates O(n).
7. Partition into < pivot and ≥ pivot. Record whether it was balanced (smaller side ≥ len/8) and whether no swaps were needed.
8. Recurse into the smaller side, loop on the larger (stack depth O(log n)).

[ < p ][p][ >= p ]        smaller side: recurse; larger side: loop
equal-heavy: pred == p ->  [ == p ][ > p ]  skip the == block entirely

Code

A compact pdqsort with the same control flow as the reference (scalar partition instead of the branchless block partition).

pub fn pdqsort<T: Ord>(v: &mut [T]) {
    let limit = usize::BITS - v.len().leading_zeros(); // about log2(n) bad partitions allowed
    recurse(v, None, limit);
}

fn recurse<'a, T: Ord>(mut v: &'a mut [T], mut pred: Option<&'a T>, mut limit: u32) {
    let (mut was_balanced, mut was_partitioned) = (true, true);
    loop {
        let len = v.len();
        if len <= 24 { insertion_sort(v); return; }
        if limit == 0 { heapsort(v); return; }
        if !was_balanced { break_patterns(v); limit -= 1; }
        let (pivot, likely_sorted) = choose_pivot(v);
        if was_balanced && was_partitioned && likely_sorted && partial_insertion_sort(v) { return; }
        if let Some(p) = pred {
            if !(*p < v[pivot]) { // pivot == predecessor: skip the run of equal elements
                let mid = partition_equal(v, pivot);
                v = &mut v[mid..]; continue;
            }
        }
        let (mid, no_swaps) = partition(v, pivot);
        was_balanced = mid.min(len - mid) >= len / 8;
        was_partitioned = no_swaps;
        let (left, right) = v.split_at_mut(mid);
        let (p, right) = right.split_at_mut(1);
        if left.len() < right.len() {
            recurse(left, pred, limit);
            (v, pred) = (right, Some(&p[0]));
        } else {
            recurse(right, Some(&p[0]), limit);
            v = left;
        }
    }
}

/// Moves the pivot to v[0], partitions v[1..] into < p and >= p; pivot ends at the returned index.
fn partition<T: Ord>(v: &mut [T], pivot: usize) -> (usize, bool) {
    v.swap(0, pivot);
    let (p, rest) = v.split_at_mut(1);
    let (p, mut l, mut r) = (&p[0], 0, rest.len());
    while l < r && rest[l] < *p { l += 1; }
    while l < r && !(rest[r - 1] < *p) { r -= 1; }
    let no_swaps = l >= r;
    loop {
        while l < r && rest[l] < *p { l += 1; }
        while l < r && !(rest[r - 1] < *p) { r -= 1; }
        if l >= r { break; }
        r -= 1; rest.swap(l, r); l += 1;
    }
    v.swap(0, l);
    (l, no_swaps)
}

/// All elements are >= pivot here; puts the ones == pivot first, returns where > pivot starts.
fn partition_equal<T: Ord>(v: &mut [T], pivot: usize) -> usize {
    v.swap(0, pivot);
    let (p, rest) = v.split_at_mut(1);
    let (p, mut l, mut r) = (&p[0], 0, rest.len());
    loop {
        while l < r && !(*p < rest[l]) { l += 1; }
        while l < r && *p < rest[r - 1] { r -= 1; }
        if l >= r { break; }
        r -= 1; rest.swap(l, r); l += 1;
    }
    l + 1
}

fn choose_pivot<T: Ord>(v: &[T]) -> (usize, bool) {
    fn med3<T: Ord>(v: &[T], mut a: usize, mut b: usize, mut c: usize, swaps: &mut u32) -> usize {
        if v[b] < v[a] { std::mem::swap(&mut a, &mut b); *swaps += 1; }
        if v[c] < v[b] { std::mem::swap(&mut b, &mut c); *swaps += 1; }
        if v[b] < v[a] { std::mem::swap(&mut a, &mut b); *swaps += 1; } b
    }
    let (len, mut swaps) = (v.len(), 0);
    let (a, b, c) = (len / 4, len / 2, len / 4 * 3);
    let m = if len > 128 { // ninther
        let a = med3(v, a - 1, a, a + 1, &mut swaps);
        let b = med3(v, b - 1, b, b + 1, &mut swaps);
        let c = med3(v, c - 1, c, c + 1, &mut swaps);
        med3(v, a, b, c, &mut swaps)
    } else { med3(v, a, b, c, &mut swaps) };
    (m, swaps == 0)
}

fn partial_insertion_sort<T: Ord>(v: &mut [T]) -> bool { // gives up after 8 moves
    let mut moves = 0;
    for i in 1..v.len() {
        let mut j = i;
        while j > 0 && v[j] < v[j - 1] { v.swap(j, j - 1); j -= 1; moves += 1; }
        if moves > 8 { return false; }
    }
    true
}

fn insertion_sort<T: Ord>(v: &mut [T]) {
    for i in 1..v.len() { let mut j = i; while j > 0 && v[j] < v[j - 1] { v.swap(j, j - 1); j -= 1; } }
}

fn break_patterns<T>(v: &mut [T]) { // swap 3 middle elements with pseudo-random positions
    let len = v.len();
    let mut seed = len as u32;
    for i in 0..3 {
        seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5;
        v.swap(len / 2 - 1 + i, seed as usize % len);
    }
}

fn heapsort<T: Ord>(v: &mut [T]) {
    fn sift_down<T: Ord>(v: &mut [T], mut node: usize) {
        loop {
            let mut child = 2 * node + 1;
            if child >= v.len() { return; }
            if child + 1 < v.len() && v[child] < v[child + 1] { child += 1; }
            if !(v[node] < v[child]) { return; }
            v.swap(node, child); node = child;
        }
    }
    for i in (0..v.len() / 2).rev() { sift_down(v, i); }
    for end in (1..v.len()).rev() { v.swap(0, end); sift_down(&mut v[..end], 0); }
}

Complexity and constants

• Comparisons on random input ≈ n log2 n × ~1.0-1.1 (median-of-3 / ninther pivots).
• The dominant cost on primitives is branch misprediction in partitioning: about 1 mispredict per element per level with the scalar partition above. Block partitioning (buffer 64 offsets of misplaced elements on each side with branch-free writes, then swap them in bulk) removes this and gives order of 1.5-2× speedup for ints/floats.
• Order of magnitude: Rust's std sort_unstable (ipnsort, a pdqsort descendant) sorts 10^7 random u64 in about 11 ns per element on an Apple M-series core.
• Stack: O(log n) frames because only the smaller side is recursed.

Efficiency

• Cost: order of 11 ns per element for Rust's sort_unstable (ipnsort, a pdqsort descendant) on 10^7 random u64 on an Apple M-series core; about n log2 n × 1.0-1.1 comparisons. Memory: in place, O(log n) stack. Bound: branch misprediction in partitioning (about 1 per element per level for the scalar partition), then memory bandwidth for large arrays.
• Levers:
  • block (branch-free) partitioning — order of 1.5-2× on ints and floats (Edelkamp & Weiß 2016) — cheap comparisons and moves
  • pattern detection (equal-to-predecessor pivot, partial insertion sort) — O(n) on sorted, reverse-sorted and few-distinct-key input (Peters 2021) — real-world, patterned data
  • sorting networks or branchless insertion for ≤ 16-32 elements — fewer mispredicts in the leaves — all sizes
  • sort keys or indices, permute once — large structs move once instead of many times — records over about 32 bytes
  • radix sort for plain numeric keys — 2-4× faster (order of) — large arrays of integers or floats
• Naive → standard → state of the art:
  • textbook quicksort, first-element pivot · O(n²) on sorted input
  • introsort (std::sort in libstdc++) · O(n log n) worst case, no pattern detection
  • pdqsort / ipnsort with block partitioning · order of 11 ns per element at 10^7 random u64; O(n) on patterns

Implementation notes

• Branchless partitioning only pays off for cheap comparisons and cheap moves (primitives, small POD); for expensive comparators the branchy version is fine, and the reference picks per type.
• Reverse-sorted detection: if the ninther made the maximum number of swaps (12), reverse the slice and treat it as likely sorted.
• Pivot equal to predecessor is a cheap equality test that only uses <; no three-way partitioning cost on normal data.
• Small sorts: production versions use sorting networks or branchless insertion for ≤ 16-32 elements.
• Comparator must be a strict weak order; Rust's newer sorts detect violations and may panic, C++ may read out of bounds.

Pitfalls

• Inconsistent comparators (NaN with <, randomized comparators): undefined order, in C++ even memory errors. Use total_cmp for floats.
• Assuming stability: equal keys get reordered; sort by (key, index) or use a stable sort.
• Panics/exceptions mid-sort: elements may be left permuted (Rust guarantees no duplication or loss; naive implementations do not).
• Sorting large structs moves them many times; sort indices or keys and permute once.

Variants and alternatives

In production

Language runtimes: Go sort.Sort/slices.Sort (since Go 1.19), Rust sort_unstable (1.20-1.80; its successor ipnsort since 1.81), Boost.Sort pdqsort, and, in databases and analytics, DuckDB and ClickHouse (both vendor pdqsort sources).

Implementations

Sources

• O. R. L. Peters, Pattern-defeating Quicksort, arXiv:2106.05123, 2021. paper · code
• S. Edelkamp, A. Weiß, BlockQuicksort: Avoiding Branch Mispredictions in Quicksort, ESA, 2016. paper
• D. R. Musser, Introspective Sorting and Selection Algorithms, Software: Practice and Experience, 1997.
• J. L. Bentley, M. D. McIlroy, Engineering a Sort Function, Software: Practice and Experience, 1993. paper
• Rust 1.81.0 release notes, New sort implementations. post
• Go 1.19 release notes (sort package uses pattern-defeating quicksort). notes