How it works?

基数ソート（Radix Sort）は、最下位の桁（1の位）から最上位の桁へと、一度に1つの桁位置を処理します。各パスでは安定（stable）なソートを使用するため、前のパスで行われた処理が維持されます。

ステップ・バイ・ステップのプロセス：

1. 安定な計数ソート（counting sort）を使用して、1の位の数字でソートします。
2. 10の位の数字でソートします。この際、同じ値がある場合は前の順序を維持します。
3. 最大数の桁位置を処理し終えるまで、100の位、1000の位と同様に続けます。

[170, 45, 75, 90, 2, 802, 24, 66] の例：

• 1の位によるソート：[170, 90, 2, 802, 24, 45, 75, 66]
• 10の位によるソート：[2, 802, 24, 45, 66, 170, 75, 90]
• 100の位によるソート：[2, 24, 45, 66, 75, 90, 170, 802]

最後の桁の後、配列は完全にソートされます。この仕組みのポイントは、上位の桁が優先される間も、安定性によって下位の桁の順序が損なわれないことです。