基数ソート — Project Hematite

カウントソートは $\Omega(n \log n)$ の比較障壁を破るが、キー範囲 $k$ が $n$ に対して小さい場合のみだ。64 ビット整数では $k = 2^{64}$ で巨大だ。基数ソートはカウントソートを桁ごとに適用し、範囲を小さく保ちながら（ $b = 10$ または $256$ ）任意の大きさの値を扱う。

最下位桁（LSD）基数ソート

基数ソートには 2 つのフレーバーがある：LSD（least-significant digit / 最下位桁）と MSD（most-significant digit / 最上位桁）。LSD はシンプルで最初に学ぶべきものだ。

アルゴリズムはデータに対して $d$ 回のパスを行う。 $d$ は最大値の桁数だ。パス $p$ では安定なサブルーチンを使って $p$ 番目の桁（0 = 1 の位、1 = 10 の位、…）でソートする。各パスが安定で最下位から最上位へ桁を処理するため、最終結果は完全にソートされる。

安定性がなぜ不可欠か

[170, 45, 75, 90, 2, 802, 24, 66] を桁ごとにソートするとする。

パス	桁	結果
0	1 の位	`[170, 90, 2, 802, 24, 45, 75, 66]`
1	10 の位	`[2, 802, 24, 45, 66, 170, 75, 90]`
2	100 の位	`[2, 24, 45, 66, 75, 90, 170, 802]` ✓

パス 1 の後、2 と 802 は 10 の位が 0 で 24 より小さいため 24 の前に来る。パス 0 からの安定性により、2（1 の位が 2）が 802（1 の位が 2）の前に来る。これにより、パス 2 が 100 の位でソートするとき、2 と 802 はすでに正しい相対順序にある。

パス 1 が不安定だったなら 2 と 802 がスワップされ、パス 0 で確立した 1 の位の順序が壊れる。

Zig 実装

const std = @import("std");

/// arr を exp の桁でソートする 1 パスのカウントソート。
/// exp = 1 → 1 の位、10 → 10 の位、100 → 100 の位、…
fn sortByDigit(arr: []u64, out: []u64, exp: u64) void {
    const base = 10;
    var counts = [_]usize{0} ** base;

    // 各桁の出現回数をカウントする。
    for (arr) |x| counts[(x / exp) % base] += 1;

    // 前置和。
    for (1..base) |i| counts[i] += counts[i - 1];

    // 安定な順序で配置する（逆順走査）。
    var i = arr.len;
    while (i > 0) {
        i -= 1;
        const digit = (arr[i] / exp) % base;
        counts[digit] -= 1;
        out[counts[digit]] = arr[i];
    }
}

/// arr をインプレースでソートする（すべての値は非負でなければならない）。
fn radixSort(arr: []u64, allocator: std.mem.Allocator) !void {
    if (arr.len == 0) return;

    const out = try allocator.alloc(u64, arr.len);
    defer allocator.free(out);

    // 何桁のパスが必要かを知るため最大値を求める。
    var max_val = arr[0];
    for (arr[1..]) |x| if (x > max_val) { max_val = x; };

    // 最下位桁から桁ごとに処理する。
    var exp: u64 = 1;
    while (exp <= max_val) : (exp *= 10) {
        sortByDigit(arr, out, exp);
        @memcpy(arr, out);
    }
}

sortByDigit は基数 10 の桁（範囲 0〜9）に限定した独立したカウントソートで、入力の値に関わらず counts 配列が固定サイズ 10 になる。

基数の選択

基数 10 は読みやすいが最速ではない。実用的には基数 256（ $b = 256$ ）がよく使われる：1 バイトが 1 桁で、32 ビット整数に 4 パス、64 ビット整数に 8 パスだ。counts 配列は 256 エントリ — まだ非常に小さく — 桁の取り出しが単純な 1 バイトシフトになる：

const digit = (x >> (8 * pass)) & 0xFF;

基数が大きいほどパス数が少なく（ $d$ が小さくなる）、counts 配列が大きくなる（ $b$ が増える）。最適な基数はこの 2 つをバランスさせる。

計算量の分析

sortByDigit の各パスは $O(n + b)$ かかる（ $b$ は基数）。 $d$ パスで：

T(n) = O\!\left(d \cdot (n + b)\right).

$w$ ビット固定長整数と基数 $b = 2^r$ の場合、パス数は $d = \lceil w / r \rceil$ ：

T(n) = O\!\left(\frac{w}{r} \cdot \left(n + 2^r\right)\right).

$w$ と $b$ が $n$ に対して定数の場合（例えば 32 ビット整数、基数 256）、これは $O(n)$ だ。

基数ソートが勝つ場面

比較ベースのソートの $O(n \log n)$ と比較すると：

$d \cdot b \ll n \log n$ のとき、つまり $d$ が小さく $b$ が $n$ に対して小さいとき基数ソートが勝つ。
32 ビット整数で $n \ge 10^6$ のとき、基数 256 の基数ソート（4 パス、256 エントリの counts 配列）は実用的にクイックソートを上回ることが多い。
64 ビット整数や可変長キー（文字列）では $d$ が増えて優位が縮む。

符号付き整数の処理

上の実装は非負（u64）キーを必要とする。符号付き整数をソートするには：

バイアス：すべての値に $|min|$ を加えて $[0, max - min]$ にシフトし、ソートして出力から $|min|$ を引く。
負と正を分ける：2 つのグループを独立してソートし、連結する（負を逆順に、次に正を）。

まとめ

LSD 基数ソートは最下位から最上位の桁へと $d$ 回のパスを行い、各回に安定なサブルーチン（カウントソート）を使う。
各パスの安定性は不可欠だ：以前の（低位の）桁で確立した順序がそれ以降の（高位の）桁のパスで保たれる。
時間計算量は $O(d \cdot (n + b))$ （ $d$ は桁数、 $b$ は基数）。
固定長整数と適切な基数に対してこれは $O(n)$ — 線形だ。
$d$ と $b$ が $n$ に対して小さい場合、基数ソートは比較ベースの $O(n \log n)$ ソートを上回る。
実装は出力バッファと counts 配列に $O(n + b)$ の余分な空間を使う。