Motivation

基数ソート（Radix Sort）は、2つの数値を直接比較することはありません。安定した補助ソートを使用して、一度に1桁ずつグループ化します。これにより、比較ソートでは超えられない O(n log n) の壁を打ち破ることができます。

なぜ基数ソートを学ぶのか？

• 線形に近い時間計算量： O(d * (n + k)) で動作します。ここで、d は桁数、k は基数（ここでは10）です。桁数が制限されている数値の場合、実質的に O(n) となります。
• 安定性： 同じ値を持つ要素の相対的な順序が維持されます。これこそが、桁ごとのパスを正しく組み合わせるために不可欠な要素です。
• 異なるアプローチ： ソートが必ずしも「比較」を意味するわけではないことを示しており、大きな整数や固定幅のキーを扱う際に重要な洞察を与えてくれます。

トレードオフ：桁に分解できるキー（ここでは非負の整数）が必要であることと、バケットのための追加メモリが必要になることです。