カウントソート — Project Hematite

これまで見てきたすべてのソート — バブル、選択、挿入、マージ — は要素のペアを比較することで動作する。任意の比較ベースのソートは最悪ケースで少なくとも $\Omega(n \log n)$ 回の比較を必要とすることが証明できる。カウントソートは要素をまったく比較しないことで、この界を完全に回避する。

比較の下界（概略）

比較ソートは二分決定木としてモデル化できる：各内部ノードが比較で、各葉が可能なソート済み順序だ。 $n$ 要素には $n!$ の可能な順序があるため、木には少なくとも $n!$ の葉が必要だ。 $n!$ の葉を持つ二分木の高さは少なくとも $\log_2(n!) = \Theta(n \log n)$ だ。よってすべての比較ソートは常に $\Omega(n \log n)$ 回の比較を使う。

カウントソートは値そのものをインデックスとして使うことでこの界を回避する — 値を比較しない。

カウントソートが適用できる条件

カウントソートには 2 つの要件がある：

整数キー — または整数にマッピングできるキー。
既知の小さな範囲 $[min, max]$ — 異なるキー値の数 $k = max - min + 1$ が $n$ に対して小さくなければならない。

$k = O(n)$ ならカウントソートは $O(n)$ 時間で動作する。 $k$ が大きい場合（例えば 32 ビット整数で $k = 2^{32}$ ）、カウント配列それ自体が入力を超える大きさになる。

3 つのフェーズ

カウントソートはデータを 3 回走査する。

フェーズ 1：カウント

長さ $k$ の counts 配列を確保してゼロで初期化する。入力を一度走査し、各要素 x に対して counts[x - min] をインクリメントする。

フェーズ 2：前置和

counts をインプレースで変換して counts[i] がキー $\le min + i$ の要素数を保持するようにする。これが各キーの最後の有効な出力位置を教えてくれる。

フェーズ 3：配置

入力配列を逆順に走査し、各要素を位置 counts[x - min] - 1 の出力に書き込み、counts[x - min] をデクリメントする。逆順に走査することで安定性が保たれる。

Zig 実装

const std = @import("std");

/// arr をインプレースでソートする。arr のすべての値は [min_val, max_val] 内でなければならない。
fn countingSort(
    arr: []i64,
    min_val: i64,
    max_val: i64,
    allocator: std.mem.Allocator,
) !void {
    const range: usize = @intCast(max_val - min_val + 1);

    // フェーズ 1：出現回数をカウントする。
    const counts = try allocator.alloc(usize, range);
    defer allocator.free(counts);
    @memset(counts, 0);

    for (arr) |x| counts[@intCast(x - min_val)] += 1;

    // フェーズ 2：前置和 — counts[i] が min_val+i 以下の要素数になる。
    for (1..range) |i| counts[i] += counts[i - 1];

    // フェーズ 3：要素を逆順に出力に配置する（安定性を保つ）。
    const out = try allocator.alloc(i64, arr.len);
    defer allocator.free(out);

    var i = arr.len;
    while (i > 0) {
        i -= 1;
        const key: usize = @intCast(arr[i] - min_val);
        counts[key] -= 1;
        out[counts[key]] = arr[i];
    }

    @memcpy(arr, out);
}

実行例

[4, 2, 2, 8, 3, 3, 1] を min_val = 1、max_val = 8（range = 8）でソートする。

フェーズ 1 後（counts はキー 1〜8 を表す添字 0〜7）：

キー：   1  2  3  4  5  6  7  8
カウント：1  2  2  1  0  0  0  1

フェーズ 2 後（前置和）：

キー：   1  2  3  4  5  6  7  8
カウント：1  3  5  6  6  6  6  7

counts[3] = 6 はキー ≤ 4 の要素が 6 つあることを意味するので、最後の 4 は出力位置 5（0 始まり）に置かれる。

フェーズ 3（入力を右から左に走査）：

arr[6] = 1：counts[0] が 0 になり output[0] に置く。
arr[5] = 3：counts[2] が 4 になり output[4] に置く。
arr[4] = 3：counts[2] が 3 になり output[3] に置く。
… と続く。

最終出力：[1, 2, 2, 3, 3, 4, 8]. ✓

逆順走査が安定性を保証する理由

前向きに走査すると同じキーの要素が逆の入力順で出力に来る — 後の重複が先に来る。逆向きに走査すると最後の重複が最初に処理され、そのキーの最後の利用可能スロットにデクリメントされ、最初の重複が最初のスロットに入る。等しい要素は入力と同じ順序で出力に現れる：安定だ。

計算量

指標	計算量
時間	$O(n + k)$
余分な空間	$O(n + k)$
安定	はい
比較ベース	いいえ

$O(k)$ の項は counts 配列の初期化とスキャンから、 $O(n)$ の項は入力の 3 回の線形走査から来る。

$k = O(n)$ のとき、合計は $O(n)$ — 線形だ。 $k \gg n$ のとき、アルゴリズムは劣化する：counts 配列のほとんどがゼロで、初期化に大半の時間を費やす。

カウントソートを使わない場合

大きなキー範囲：任意の 32 ビット符号付き整数のソートには $k = 2^{32} \approx 4 \times 10^9$ のエントリが必要 — 32 GB の counts 配列。実用的でない。
整数でないキー：浮動小数点数や文字列キーは直接インデックスとして使えない。代わりに比較ベースのソートを使う。
未知の範囲：min_val と max_val が事前にわからない場合、それらを求めるための余分な走査が必要（まだ $O(n)$ だが複雑さが増す）。

まとめ

カウントソートは出現回数をカウントし、前置和で出力位置を求め、各要素を正しいスロットに配置する。
比較ベースでないため $\Omega(n \log n)$ の下界を下回る。
時間と空間はともに $O(n + k)$ （ $k$ はキー範囲）。
安定だ：フェーズ 3 の逆順走査が等しい要素の元の順序を保つ。
$k = O(n)$ のとき実用的、 $k$ が大きい場合やキーが整数でない場合は実用的でない。
基数ソートはカウントソートを安定なサブルーチンとして使い、任意のサイズの整数キーを桁ごとにソートする。