計算量理論の分野です。比較によらないソートバケットソートデータが上限のある整数のような場合に用いる。データの種類が定数種類しかない場合には、ハッシュ関数で整数に変えてから用いてもよい。桁毎にバケットソートをしてソートする。0からm-1の整数という性質を満足するとしましょう。(例えば、学籍番号の下2桁とか。)方針m個のバケット(配列)を用意して、データを振り分けていく。データそのものを配列の添字として使う。B[m-1]バケットソートの実現/*概略です。i;/*カウンタ*/for(i=0;i<n;i++){B[A[i]]=i;}return;}i番目のデータの参照は、A[B[i]]で行う。重複した分を、リストとして繋ぐ。(外部ハッシュ法参照。重複データのリストへの挿入順序が大事。(外部ハッシュでは、余り重要ではなかったが。5先入れ先出しのキューにしておいたほうがいいです。配列1回のアクセスには、定数時間で実行できる。(RAMモデルの能力を最大限に使っていることに注意しましょう。)繰り返し回数は、明らかにデータ数n回です。n)のアルゴリズムです。桁毎にバケットソートをしてソートする。下位桁から順にバケットソートする。/*バケットソートを第k桁でソートして、もとの配列に戻すように拡張する。