Non-Comparison Sorts: Counting Sort, LSD/MSD Radix Sort & Bucket Sort

Counting Sort & Prefix-Sum Stability

When keys are integers in a small range $[0, k)$, Counting Sort bypasses key-to-key comparisons entirely in three linear passes:

1. Histogram Pass ($\Theta(n)$): Count occurrences of each key in count[0 .. k-1].
2. Prefix-Sum Pass ($\Theta(k)$): Compute exclusive or inclusive prefix sums so count[v] holds the exact starting (or ending) output index for records with key $v$.
3. Stable Scatter Pass ($\Theta(n)$): Iterate through the input array and place each element into out[count[key]++] (using exclusive prefix sums in a forward scan, or inclusive prefix sums in a backward scan).

Choosing the Optimal Radix $b = 2^r$ & Sorting Signed/Floating-Point Keys

Given $n$ keys of $w$ bits, if we extract $r$ bits per pass ($b = 2^r$ buckets), we perform $d = w/r$ passes of cost $\Theta(n + 2^r)$. Theoretically, choosing $r = \lfloor \log_2 n \rfloor$ ($b = \Theta(n)$) minimizes $\frac{w}{r}(n + 2^r)$ to $\Theta\!\left(\frac{w}{\log_2 n} \cdot n\right)$. In hardware practice, however, $r = 8$ ($b = 256$ buckets, 4 passes for 32-bit ints, 8 passes for 64-bit ints) is almost universally used because a $256 \times 4\text{ B} = 1\text{ KB}$ histogram array stays permanently pinned in L1d cache and avoids TLB thrashing!

Can Radix Sort handle negative two's-complement integers and IEEE-754 float/double values? Yes—via bijective order-preserving bit flips in $O(1)$ instructions:

• Signed Two's-Complement int32_t / int64_t: Flipping the sign bit (uint64_t(x) ^ (1ULL << 63)) maps $-2^{63} \mapsto 0$, $-1 \mapsto 2^{63}-1$, $0 \mapsto 2^{63}$, and $2^{63}-1 \mapsto 2^{64}-1$, turning signed order into unsigned lexicographical order!
• IEEE-754 double (Sign-Magnitude Exponent + Mantissa): Positive floats already sort identically to unsigned integers ($+0.0 < +1.0 < +\infty$). Negative floats have MSB = $1$ and increase in magnitude as they become more negative (reversed order). Michael Herf's FloatFlip bijection flips all 64 bits if the sign bit is $1$, and flips only the sign bit if the sign bit is $0$: uint64_t mask = -int64_t(u >> 63) | (1ULL << 63); return u ^ mask;.

Production C++20 Implementation: 8-Bit LSD Radix Sort with Signed/Float Bijection & Pass-Skipping

#include <algorithm>
#include <array>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <vector>

// Bijective order-preserving projections to uint64_t
constexpr std::uint64_t radix_encode_int64(std::int64_t x) noexcept {
    return static_cast<std::uint64_t>(x) ^ (1ULL << 63);
}
constexpr std::int64_t radix_decode_int64(std::uint64_t u) noexcept {
    return static_cast<std::int64_t>(u ^ (1ULL << 63));
}

constexpr std::uint64_t radix_encode_double(double d) noexcept {
    std::uint64_t u = std::bit_cast<std::uint64_t>(d);
    std::uint64_t mask = -static_cast<std::int64_t>(u >> 63) | (1ULL << 63);
    return u ^ mask;
}
constexpr double radix_decode_double(std::uint64_t u) noexcept {
    std::uint64_t mask = ((u >> 63) - 1ULL) | (1ULL << 63);
    return std::bit_cast<double>(u ^ mask);
}

// High-throughput 64-bit LSD Radix Sort (r = 8 bits, 1 histogram pass + skipped trivial passes)
void radix_sort_u64(std::vector<std::uint64_t>& a) {
    const std::size_t n = a.size();
    if (n <= 1) return;

    // 1. Compute all 8 byte histograms in a single sequential scan (8 KB fits in L1d)
    std::array<std::array<std::size_t, 256>, 8> count{};
    for (std::uint64_t v : a) {
        for (std::size_t p = 0; p < 8; ++p) {
            ++count[p][(v >> (p * 8)) & 0xFFU];
        }
    }

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

    for (std::size_t p = 0; p < 8; ++p) {
        // 2. Convert histogram to exclusive prefix sums & detect trivial single-bucket pass
        bool trivial = false;
        std::size_t sum = 0;
        for (std::size_t b = 0; b < 256; ++b) {
            if (count[p][b] == n) { trivial = true; break; }
            std::size_t c = count[p][b];
            count[p][b] = sum;
            sum += c;
        }
        if (trivial) continue; // All elements have identical byte p!

        // 3. Stable scatter pass
        const std::size_t shift = p * 8;
        for (std::size_t i = 0; i < n; ++i) {
            const std::uint64_t v = src[i];
            const std::size_t bucket = (v >> shift) & 0xFFU;
            dst[count[p][bucket]++] = v;
        }
        std::swap(src, dst);
    }

    if (src != a.data()) {
        std::copy(src, src + n, a.data());
    }
}