Thirteen Elements, Forty-Five Comparisons: The Sorting Network in Rust's sort

TL;DR: Rust’s sort and sort_unstable both fall back to a fixed sorting network for small inputs — up to 13 elements, 45 compare-exchanges — instead of insertion sort. A network has no branches at all: the comparison sequence is fixed in advance, so there is nothing to mispredict.

The rule

rust
// library/core/src/slice/sort/stable/mod.rs:28-86

#[inline(always)]
pub fn sort<T, F: FnMut(&T, &T) -> bool, BufT: BufGuard<T>>(v: &mut [T], is_less: &mut F) {
    // Arrays of zero-sized types are always all-equal, and thus sorted.
    if T::IS_ZST {
        return;
    }

    // Instrumenting the standard library showed that 90+% of the calls to sort
    // by rustc are either of size 0 or 1.
    let len = v.len();
    if intrinsics::likely(len < 2) {
        return;
    }
    ...
            // More advanced sorting methods than insertion sort are faster if called
            // in a hot loop for small inputs, but for general-purpose code the small
            // binary size of insertion sort is more important. The instruction cache in
            // modern processors is very valuable, and for a single sort call in general
            // purpose code any gains from an advanced method are cancelled by i-cache
            // misses during the sort, and thrashing the i-cache for surrounding code.
            const MAX_LEN_ALWAYS_INSERTION_SORT: usize = 20;
            if intrinsics::likely(len <= MAX_LEN_ALWAYS_INSERTION_SORT) {
                insertion_sort_shift_left(v, 1, is_less);
                return;
            }

Note the reasoning about insertion sort for the stable sort: the reason is not that insertion sort is faster, but that it is small, and the instruction cache is precious. For the unstable sort (ipnsort) the trade goes the other way — a network is branchless and therefore fast.

The network

rust
// library/core/src/slice/sort/shared/smallsort.rs:463-530

/// Sorts the first 13 elements of `v` with a fast fixed function.
///
/// Should `is_less` generate substantial amounts of code the compiler can choose to not inline
/// `swap_if_less`. If the code of a sort impl changes so as to call this function in multiple
/// places, `#[inline(never)]` is recommended to keep binary-size in check. ...
fn sort13_optimal<T, F>(v: &mut [T], is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    if v.len() < 13 {
        intrinsics::abort_immediate();
    }
    let v_base = v.as_mut_ptr();
    // Optimal sorting network see:
    // https://bertdobbelaere.github.io/sorting_networks.html.
    unsafe {
        swap_if_less(v_base, 0, 12, is_less);
        swap_if_less(v_base, 1, 10, is_less);
        ...
        swap_if_less(v_base, 5, 6, is_less);
    }
}

Dobbelaere’s optimal 13-element network is 45 compare-exchange operations — provably minimal for 13 inputs. The network is data independent: the same 45 comparisons happen regardless of the input, so the branch predictor never has anything to learn.

swap_if_less compiles to a compare and a conditional swap:

rust

// library/core/src/slice/sort/shared/smallsort.rs

typically becoming a cmov-style branchless select for small Copy types.

The specialisation gate

The network is only used for types that are Copy and small enough to be handled with stack buffers:

rust

// library/core/src/slice/sort/shared/smallsort.rs:142-171

with a stack budget:

rust
const MAX_STACK_ARRAY_SIZE: usize = 4096;

The specialisation matters because the network’s swap_if_less needs the elements to be movable without a destructor; for types with Drop the stable path uses a different, copy-based small sort.

Ping-pong scratch

For the stable sort, small sorts use a scratch buffer in a ping-pong fashion, and the merge-back is panic-safe:

rust
// library/core/src/slice/sort/shared/smallsort.rs:220-309

fn small_sort_general_with_scratch<T: FreezeMarker, F: FnMut(&T, &T) -> bool>(
    v: &mut [T],
    scratch: &mut [MaybeUninit<T>],
    is_less: &mut F,
) {
    ...
        // SAFETY: see comment in `CopyOnDrop::drop`.
        let drop_guard = CopyOnDrop { src: scratch_base, dst: v_base, len };

CopyOnDrop is the same pattern as the DropGuard in Vec::drain: if the comparison function panics, the guard still copies the scratch data back into the original array so the Vec is left in a valid state.

Where it lives

library/core/src/slice/sort/shared/smallsort.rs — sort13_optimal, CopyOnDrop, the specialisation gates.
library/core/src/slice/sort/stable/mod.rs — the stable sort’s small-input policy.
library/core/src/slice/sort/unstable/mod.rs — ipnsort, the unstable variant.

Takeaway

Data-dependent branches are the enemy of small sorts. A fixed comparison network does strictly more comparisons than insertion sort in the worst case, but it has zero unpredictable branches, and for small inputs the branch mispredictions cost more than the extra work. This is a classic case where “more operations, fewer branches” wins — and where the optimal network (45 rather than 60-something comparisons) is a nice piece of applied combinatorics.