基数ソート — O(n log n)の壁を破る

基数ソートの動作原理

基数ソートは非比較ベースのソートアルゴリズムです。要素同士を比較する代わりに、キーの個々の桁（または文字）を最下位桁から最上位桁（LSD）またはその逆（MSD）の順に処理してソートします。

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

function radixSort(arr):
  maxVal = max(arr)
  for exp = 1 while maxVal / exp > 0, exp *= 10:
    countingSort(arr, exp)

各パスでは、1つの桁位置でソートするために安定なサブルーチンとしてカウンティングソートを使用します。安定性は重要です — 前のパスの順序が保持されることを保証します。

桁ごとの例

[170, 45, 75, 90, 802, 24, 2, 66] をソート：

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

計算量

指標	値
時間	O(n * k)、k = 桁数
空間	O(n + b)、b = 基数（通常10または256）
安定	はい
インプレース	いいえ

基数ソートが比較ソートに勝つ場合

比較ベースソートの理論的下限はO(n log n)です。基数ソートは要素を比較しないことでこれを回避します。以下の場合に高速です：

• k（桁数）がlog nに対して小さい場合
• 32ビット整数の場合、k = 32/log₂(基数)。基数256使用時：k = 4
• n > 2⁴ = 16の場合、基数256の基数ソートはより少ない操作で完了

MSD vs LSD

• LSD（最下位桁優先）: 右端の桁から処理。実装が簡単で、自然に安定。
• MSD（最上位桁優先）: 左端の桁から処理。キーに共通のプレフィックスがある場合にショートカット可能。文字列ソートに使用。