基数ソートのシミュレーションシミュレータでは最大3桁の整数値(0~999)をソートします。動き自体はバケットソートと変わらないのですが、1桁目の値から順に3度バケットソートが実行されているのがわかります。アルゴリズムの解説10進数版(0~999)最大3桁の整数値(0~999)についてのデータを基数ソートでソートする場合を考えます。基数の取りうる値(k=10)の数だけバケツを用意します。ソート対象データについて1桁目をキーにバケットソートを実行します。2桁目、3桁目についても同様にバケットソートを実行します。ビット列版(応用)通常コンピュータの内部データは10進数ではなく、4バイトや8バイトのビット列です。したがって、10進数の乗除算よりも、ビット演算を使用する方が処理コストが低く済みます。上記の10進数の基数ソートでは、k桁目を求める際に商と余りを求める計算を行う必要がありますが、これをビット演算に置き換えてみます。32bit整数値は4バイトなので、1バイト毎にバケットソートを適用すれば4回のソートで済むうえ、ビット演算を使うことで高速な処理が期待できます。2バイト目を取り出すには、8ビット分右シフトして255(1バイト)でマスク演算します。すると2バイトの値が計算できます。具体的にはサンプルコードを参照してください。