Radix sort

Deep dive

How it works

In: n fixed-width keys (or key-index pairs), mapped to unsigned order · Out: the keys sorted · State: a second buffer of n records and 8 histograms of 256 counters (LSD) · Cost: O(n·w/d): 4 passes for u32, 8 for u64

LSD (least significant digit first), digit width 8 bits:

1. One pass over the keys builds all histograms at once (hist[digit][byte]).
2. For each digit d (low to high): skip if one bucket holds all n keys; else prefix-sum hist[d] into offsets, scatter each key from src to dst[offset[b]++], swap buffers.
3. Stability of each pass is what makes the final order correct.

MSD (most significant first): partition by the top digit into 256 buckets, then recurse into each bucket; buckets smaller than a threshold are finished with insertion sort. In place via American flag sort (cycle-swap elements into their buckets).

Key transforms (to unsigned with the same order):

i64:  x as u64 ^ (1 << 63)                         flip sign bit
f64:  b = bits(x); if sign set { !b } else { b | 1<<63 }   negative: flip all; positive: flip sign

Code

/// Stable LSD radix sort of records by a u64 key, 8-bit digits.
pub fn radix_sort_by_key<T: Copy, F: Fn(&T) -> u64>(v: &mut Vec<T>, key: F) {
    let n = v.len();
    if n < 256 { v.sort_by_key(|x| key(x)); return; } // stable, like the radix sort
    let mut hist = vec![[0usize; 256]; 8];
    for x in v.iter() {
        let k = key(x);
        for d in 0..8 { hist[d][(k >> (8 * d)) as usize & 0xFF] += 1; }
    }
    let mut buf: Vec<T> = v.clone();
    for d in 0..8 {
        if hist[d].iter().any(|&c| c == n) { continue; } // every key has the same byte here
        let (mut off, mut sum) = ([0usize; 256], 0);
        for b in 0..256 { off[b] = sum; sum += hist[d][b]; }
        for x in v.iter() {
            let b = (key(x) >> (8 * d)) as usize & 0xFF;
            buf[off[b]] = *x;
            off[b] += 1;
        }
        std::mem::swap(v, &mut buf);
    }
}

/// Order-preserving maps to u64.
pub fn key_i64(x: i64) -> u64 { x as u64 ^ (1 << 63) }
pub fn key_f64(x: f64) -> u64 { // same order as f64::total_cmp (-NaN < -inf < -0 < +0 < inf < NaN)
    let b = x.to_bits();
    if b >> 63 == 1 { !b } else { b | (1 << 63) }
}

pub fn sort_u32(v: &mut Vec<u32>) { radix_sort_by_key(v, |&x| x as u64) } // high 4 passes skipped
pub fn sort_f64(v: &mut Vec<f64>) { radix_sort_by_key(v, |&x| key_f64(x)) }

Complexity and constants

• Work: passes × n × (1 read + 1 scattered write) + one histogram pass. For 10^8 u32 keys: 4 passes × 800 MB moved ≈ 3.2 GB of traffic, order of 0.3-0.5 s on one core, versus order of 1-1.5 s for a fast comparison sort (about 27 levels of comparisons).
• Measured (10^7 random keys, one Apple M-series core, Rust std sort_unstable at ≈ 11 ns/key): the code below takes ≈ 6 ns/key for u64 (2×) and ≈ 3 ns/key for u32 (4×). Tuned libraries widen the gap.
• Digit width: 8 bits → 256 buckets, whose write heads stay in L1 and the TLB. 11 bits (2,048 buckets) saves a pass for 32-bit keys (3 instead of 4) but scatters into too many streams for large n unless writes are buffered.
• Memory: LSD needs a second buffer of n records; histogram 8 × 256 × 8 bytes = 16 KB.

Efficiency

• Cost: measured on 10^7 random keys, one Apple M-series core: about 6 ns/key for u64 and 3 ns/key for u32 with the code below, against about 11 ns/key for Rust's sort_unstable. Traffic: passes × n × (1 read + 1 scattered write); 10^8 u32 keys move about 3.2 GB (order of 0.3-0.5 s on one core). Memory: 2× the data for LSD, 16 KB of histograms. Bound: memory bandwidth and scatter write streams.
• Levers:
  • skip passes where all keys share the byte — fewer passes — clustered or small-range keys
  • write-combining buffers (8-16 keys per bucket, flush full lines) — often 1.5-2× for large n (order of) — arrays beyond cache
  • sort (key, index) pairs, permute once — 8-16 bytes moved per element — big records
  • per-thread histograms plus a global prefix sum; on GPUs Onesweep's single pass per digit (Adinets & Merrill 2022) — multi-core and GPU
  • in-place MSD (American flag, ips2ra) — no second buffer (Axtmann et al. 2022) — tight memory
• Naive → standard → state of the art:
  • comparison sort · about 11 ns/key at 10^7 u64 (sort_unstable)
  • LSD radix sort, 8-bit digits · about 6 ns/key (u64), 3 ns/key (u32), measured above
  • write-combining, parallel or GPU radix sort · tuned libraries widen the gap (Adinets & Merrill 2022)

Implementation notes

• Write-combining buffers: stage 8-16 keys per bucket in a small L1 buffer and flush full cache lines; avoids read-for-ownership traffic and TLB misses on the scatter, often 1.5-2× faster for large n.
• Sort (key, index) pairs, not big records: move 8-16 bytes per element, then permute once (or not at all).
• Parallel LSD: per-thread histograms over chunks, a global prefix sum over (bucket, thread), then each thread scatters its chunk; GPU Onesweep does this with decoupled look-back in a single pass per digit.
• MSD for skewed or long keys: stops early when buckets become small; American flag / ips2ra sort in place with block-wise permutation.
• Hybrid: one MSD pass to split into 256 cache-sized buckets, then LSD or comparison sort within each bucket (cache-friendly for huge arrays).
• Pre-check: skip passes with constant digits, and check if the input is already sorted in the histogram pass.

Pitfalls

• Sorting floats by raw bits: negatives come out reversed and after positives. Use the transform above; decide where NaNs go.
• Signed integers without flipping the sign bit put negatives last.
• An odd number of performed passes leaves the result in the scratch buffer; swap handles (as above) or copy back.
• Large digit widths on big arrays thrash TLB and caches; measure, do not assume fewer passes is faster.
• Many duplicate or clustered keys make one bucket huge: fine for LSD, but MSD recursion needs a fallback.

Variants and alternatives

In production

GPU and HPC: NVIDIA CUB / Thrust DeviceRadixSort (Onesweep), databases: DuckDB's sort for ORDER BY (radix sort on normalized keys), ClickHouse (radix sort for numeric columns); libraries: Rust crates voracious_radix_sort and rdst, Boost.Sort spreadsort (hybrid radix).

Implementations

Sources

• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., 1998 (section 5.2.5).
• P. M. McIlroy, K. Bostic, M. D. McIlroy, Engineering Radix Sort, Computing Systems, 1993.
• D. Merrill, A. Grimshaw, High Performance and Scalable Radix Sorting, Parallel Processing Letters, 2011.
• A. Adinets, D. Merrill, Onesweep: A Faster Least Significant Digit Radix Sort for GPUs, arXiv:2206.01784, 2022. paper · code
• M. Axtmann, S. Witt, D. Ferizovic, P. Sanders, Engineering In-place (Shared-memory) Sorting Algorithms, ACM Transactions on Parallel Computing, 2022. paper · code
• DuckDB blog, Fastest Table Sort in the West: Redesigning DuckDB's Sort (radix sort on normalized keys). post