Time and Space Complexity

時間計算量:

• O(d * (n + k))
  • ここで n は要素数、k は基数 (10)、d は最大値の桁数です。d 回のパスのそれぞれで O(n + k) の処理が行われます。
• d が小さく固定されている場合、これは O(n) のように動作し、比較ソートの O(n log n) よりも高速です。

空間計算量:

• O(n + k)
  • 各パスでサイズ n の出力配列とサイズ k のカウント配列を構築します。

まとめ:

• 基数ソート（Radix Sort）は、安定した非比較ソートであり、桁数が制限された整数キーに対して O(n log n) を上回ることができます。
• 桁に分割できるキーと追加のメモリが必要であり、このバージョンでは非負の整数を想定しています。