基数ソート とは？

いい質問！基数ソートは数値を桁ごとに分解して、1の位から順にバケット（箱）に振り分けるんだ。例えば 0〜9 の10個のバケットを用意して、1の位の値でまず振り分け、次に10の位、100の位…と繰り返す。全部の桁を処理し終わると自然にソートが完了するよ。

たとえば [170, 45, 75, 90, 802, 24, 2, 66] をソートするなら、まず1の位で振り分けると 170→90→802→2→24→45→75→66 の順になる。次に10の位で振り分けて、最後に100の位で振り分けると完成だよ。

データ次第だね。比較ソートの下限は O(n log n) だけど、基数ソートは O(n × k) で、k は最大桁数。桁数が小さいデータが大量にある場合は O(n) に近くなって圧倒的に速いよ。ただし桁数が多いデータだと逆に不利になることもあるんだ。

整数の大量ソート、郵便番号、IPアドレス、固定長の文字列なんかに向いてるよ。実際にデータベースエンジンや並列ソートでも使われることがあるんだ。

LSD（Least Significant Digit）は下の桁から処理する方式で、さっき説明したのがこれ。MSD（Most Significant Digit）は上の桁から処理して、途中で再帰的にグループを分割するよ。LSD のほうが実装がシンプルで安定ソートになるから一般的だね。

実はGPU上の並列ソートで基数ソートは超メジャーなんだ。NVIDIA の CUB ライブラリにも実装されていて、数十億要素のソートを高速にこなすよ。各桁の振り分け処理が並列化しやすいのが理由だね。