基数ソート（Radix Sort）とは — LSD/MSDの違い、計算量、実装と最適化ガイド
エバープレイ編集部基数ソートとは — 概要
基数ソート（基数ソート、radix sort）は、数値や文字列などのキーを桁（基数＝digit／radix）ごとに処理して整列する非比較型ソートアルゴリズムです。キーの各桁を複数回の安定な部分ソート（通常はカウントソート）で並べ替えることで、全体を整列します。比較ベースのソート（クイックソート、マージソートなど）が比較回数に下限 O(n log n) を持つのに対し、キーが有限長（桁数が定数）である場合、基数ソートは O(n) に近い計算量で高速に動作する特性があります。
基本的な考え方
基数ソートの核心は「桁単位の安定ソートを繰り返す」ことにあります。各要素の右端（最下位）あるいは左端（最上位）から一桁ずつ取り出し、それらの桁の値で安定ソートを行うと、最終的に全体が整列されます。実装上は以下の2種類が代表的です。
- LSD（Least Significant Digit）方式：最下位桁から始めて上位桁へ向かって処理する方式。整数のソートでよく使われます。各パスは安定である必要があります。
- MSD（Most Significant Digit）方式：最上位桁から始め、同じ桁のグループごとに再帰的に処理する方式。文字列の辞書順ソートや可変長キーのソートに適します。
アルゴリズムの流れ（LSD方式の典型例）
代表的な実装は、各桁の値が取り得る範囲（基数 b、例えば10進数なら b=10）を利用してカウントソートを用いる方法です。概略は次のとおりです。
- 最大値の桁数 k を求める（固定長であれば既知）。
- 最下位桁から始め、各桁について以下を行う：
- 各要素のその桁の値を数える（カウント配列 サイズ b）。
- カウント配列を累積和にして安定に位置決めできるようにする。
- 元配列を走査して桁値に基づき出力配列へ安定にコピーする。
- 出力配列を元配列に戻す（次の桁の処理へ）。
- 全 k パスを終えると整列が完了する。
計算量と空間計算量
典型的な実装（各桁に対してカウントソートを使う場合）の計算量は O(k (n + b))、ここで n は要素数、k は桁数、b は基数（たとえば 10、256 など）です。固定長の整数（例えば 32bit）を扱う場合、k は定数（例えばバイト単位で処理すれば k=4）であり、時間計算量は O(n) とみなせます。
空間計算量は、カウント配列の O(b) と出力用の補助配列 O(n) が必要で、合計で O(n + b) です。in-place な実装や階層的にバケット分割する手法（American Flag Sort など）で補助メモリを削減する試みもありますが、実装の複雑さが増します。
安定性の重要性
LSD方式の正しさは「各パスでのソートが安定であること」に依存します。安定ソートであれば、上位桁をまだ処理していない段階で上位桁の相対順序が保持されるため、下位桁の処理を積み重ねることで最終的に全体の整列が得られます。多くの場合、各パスにカウントソート（安定）を用いるのが定石です。
基数（b）の選び方とトレードオフ
基数 b を何にするかは実装の性能に大きく影響します。b を大きくするとパス数 k は少なくなりますが、各パスでのカウント配列の大きさが増え、メモリ・初期化・キャッシュ性能が悪化する可能性があります。逆に b を小さくするとパス数が増え、読み書き回数が増えるため実行時間が伸びます。
実装上の典型例は「バイト単位（b=256）で 32bit/64bit 整数を処理する」や、「10進で人間向けの表示桁で処理する」などです。CPU キャッシュやSIMD、並列化のしやすさも考慮して選びます。
負の数・浮動小数点・文字列の扱い
- 負の整数：簡単な方法は正負で配列を二分して符号ごとに処理し、負の数は絶対値でソート後に逆順で結合する方法です（負の数は大小関係が逆になるため）。または、符号ビットをオフセットして扱うやり方もあります。
- 浮動小数点数（IEEE-754）：ビット表現を整数に再解釈してソートする方法が一般的です。ただし符号順序を保つためにビット変換が必要です（32-bit float の場合、符号ビットが1（負）の値はビット反転、符号ビットが0（正）の値は符号ビットを反転する（XOR 0x80000000）等）。これによりビット列の辞書順と数値順が一致します。
- 文字列：MSD 方式が一般的で、先頭の文字（あるいはバイト）から再帰的にグループ分けしていきます。可変長キーでは終端文字（または長さ情報）を扱う必要があります。辞書順やロケール依存の順序は別途考慮が必要です。
実装上のポイントと最適化
- 各パスでの読み書きは連続メモリアクセスになるためキャッシュフレンドリーに実装すると高速。逆にバケツにポインタを追加して分散させる実装はキャッシュミスが増える。
- ループのアンローリングやバイト単位での処理、SIMD を用いたカウントの並列化で高速化できる。
- MSD の再帰は小さなバケットでオーバーヘッドが大きくなるため、ある閾値以下なら別のソート（挿入ソートなど）に切り替えるハイブリッドが有効。
- 外部メモリ（ディスク）向けにはバッファリングやブロック単位の処理が重要。基数ソートはバッファを工夫すれば外部ソートに適する場合がある。
並列化・GPUでの利用
基数ソートは各パスでデータの集計（カウント）と再配置を行うため、並列化や GPU 実装との親和性が高いです。現代の並列ライブラリや GPU フレームワーク（NVIDIA Thrust / CUB など）は高速な並列ラジックスソートを提供しており、大規模データや高次元データのソートに用いられます。
出力例（簡単な疑似コード、LSD + カウントソート）
for d = 0 to k-1:
count[0..b-1] = 0
for i = 0 to n-1:
digit = extract_digit(a[i], d)
count[digit]++
accumulate count to positions
for i = n-1 downto 0: # 逆向きに処理して安定性を確保
digit = extract_digit(a[i], d)
out[--count[digit]] = a[i]
copy out back to a基数ソートが向く場面・向かない場面
- 向いている場面：固定長の整数やバイナリキー（IP アドレス、ID）、大量のデータを一様にソートする場合、GPUやマルチコアで並列化して高速化したい場合。
- 向かない場面：キーが可変で桁数が大きく（またはキー長が n に依存して成長する）比較ソートよりも非効率になる場合や、メモリ制約で補助配列が取れないケース。
実務上の注意点と落とし穴
- 理論的な O(n) 性能は「桁数が定数であること」が前提。可変長文字列のように平均的に桁数が増えると効果が薄れる。
- 基数 b を大きくしすぎるとカウント配列のクリア（ゼロ化）コストやキャッシュミスがネックになる。
- 負の値や浮動小数点は注意してビット操作やオフセット処理を行う必要がある。
- 実装の正しさは安定性に依存するため、各パスでの安定な配置を厳守すること。
まとめ
基数ソートは、キーが有限長（特に固定長）の場合に非常に効率的なソート手法です。LSD と MSD の二つの基本方針があり、用途やデータ特性によって使い分けます。実装上は基数の選択、安定な部分ソート（通常はカウントソート）、メモリとキャッシュ効率、並列化のしやすさが性能を左右します。整数や文字列、大規模並列環境でのソートでは比較ソートよりも有利になることが多く、実務でも広く使われています。
