基数ソートの仕組み・コード・計算量をわかりやすく解説

基数ソートが解決する問題

計数ソートは線形時間ですが、キーの範囲全体と同じ大きさのカウント配列が必要で、32ビットや64ビットの整数では不可能です。基数ソートは各キーを小さな桁に分割して、桁ごとに計数ソートを1回ずつ実行するため、各パスで必要なカウント配列は b 個の要素だけです（10進数の桁なら10、バイトなら256）。

小さな記号の固定された列に分解できるキーなら何にでも使えます。非負の整数、YYYYMMDD の形で書かれた日付、郵便番号のような固定長のコード、IPアドレス、固定幅の文字列などです。

具体例：10進数でのLSD基数ソート

[170, 45, 75, 90, 802, 24, 2, 66] をソートします。最大の数は3桁なので、パスは3回です。各パスは1つの桁による安定ソートで、同じ桁の要素は前のパスの順序を保ちます。

2回目のパスの後、数は下2桁でソートされています。3回目のパスでは、2、24、45、66、75、90 の100の位はすべて 0 で、安定性により、2回目のパスで得られた順序が保たれます。各パスが安定でなければならないのはこのためです。

Pythonでの実装

def counting_pass(nums, exp, base):
    """Stable counting sort of nums by the digit at exp."""
    count = [0] * base
    for x in nums:
        count[(x // exp) % base] += 1
    for d in range(1, base):
        count[d] += count[d - 1]
    out = [0] * len(nums)
    for x in reversed(nums):
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers."""
    if not nums:
        return []
    exp, biggest = 1, max(nums)
    while biggest // exp > 0:
        nums = counting_pass(nums, exp, base)
        exp *= base
    return nums

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([3, 0, 1, 0], base=256))   # [0, 0, 1, 3]

基数に 256 を使うと、各パスで1バイトを見ることになり、32ビット整数ならパスはわずか4回で済みます。負の数を含めるには、負の値と非負の値を別々にソートして連結するか、すべてのキーを最小値の分だけオフセットします。固定長の文字列では、位置 i の文字コードを桁として使い、最後の位置から最初の位置へ向かって処理します。

時間計算量と空間計算量

d が定数（固定幅のキー）で、b が n に近い値か 256 のような固定値であれば、時間は O(n) です。n 個のキーがすべて異なる場合、d は少なくとも log_b n でなければならないため、任意の大きさのキーでは基数ソートも O(n log n) を超える速さにはなりません。それでも高速なのは、各ステップが単純な配列操作だからです。

基数ソートと他のソートの比較

表中の n はキーの数、k は計数ソートのキーの範囲、d は桁数、b は基数です。LSD基数ソートは、すべての桁のパスが安定である限り、安定です。キーの構造が固定されている必要がありますが、マージソートやクイックソートのような比較ソートは、独自の比較関数を含め、どんな順序づけでも扱えます。

LSD と MSD の違い、よくある間違い

基数ソートを使う場面

基数ソートは、固定幅の整数やキーの大きな配列に適しています。32ビットのID、タイムスタンプ、IPv4アドレス、固定長の文字列などです。特に、規則的なメモリアクセスが効くGPUや高性能ライブラリで有効です。接尾辞配列の構築や、一部のデータベースやグラフィックスの処理でも使われています。通常のPythonのリストでは、最適化されたCコードで動く sorted() のほうが、実際にはほぼ常に速くなります。面接では、線形時間でソートする方法を問われたとき、たとえば Maximum Gap の問題で基数ソートが登場します。