バケットソート（）は、ソートのアルゴリズムの一つ。バケツソート、分布数えソート、計数ソート、ビンソート（）などともいう。オーダーはO("n")と高速だが、一般的なソートとは異なり、ソート対象が全順序というだけではなく「取りうる値がm種類である」というような、より強い制限を前提としている非比較ソートに分類される一つである（あるいは事前にスキャンして分布を調べるなど、モディファイを追加する必要がある）。整列したいデータの取りうる値がm種類であるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づける。元のデータ列を走査して、各データを対応するバケツに入れていく。この処理が終わった後、整列したい順序に従ってバケツから値を取り出せば、データをソートすることができる。安定ソートを実現するためには、同じバケツに入っているデータは入れたときと同じ順序で取り出す必要がある。順序が保存されない場合は、ソートはできるが、安定ソートではなくなる。後述するように基数ソートと組み合わせて使うためには、安定ソートになっている必要がある。バケットソートには、大きく分けて2種類の実装がある。まずひとつは、可変個の要素を保持できるデータ構造を使ってバケツを表現する方法である。簡単な例としては、m個の線形リストを使う実装が考えられる。直感的に理解しやすい実装だが、単純な配列だけではなく可変長のデータ構造が必要になるため、可変長のデータ構造がない言語の場合、その実装コストを考慮しておく必要がある。もうひとつは、いったん整列対象のデータを走査して値ごとの出現回数を数えておき、それに応じてひとつの配列の中を値ごとに分割する方法である。この実装によるバケットソートのみを指して特に分布数えソートと言う。例えば以下の入力が与えられたとする。昇順にソートした結果は以下のようになるはずである。さて値ごとの出現分布を調べると、1が3個、2が5個、3が4個出現していることがわかる（ソートしなくても元のデータ列に一通りアクセスすればわかる）。出現個数がわかれば、1は結果列の1番から、2は4番から、3は9番から始まることがわかる。Javaによるサンプルコードは以下のようになる。仮に32ビット整数をソートする場合に、約43億個のバケツを持つことは非現実的である。バケツは1つの値に対して1つのバケツを用意する必要はなく、範囲を持ったバケツが矛盾なくソートされていれば良い。この時、各バケツの中身は別ソートアルゴリズムでソートしてあげるか、再度バケットソートを適用する必要がある。冒頭の32ビット整数を1ビットずつ再帰的にバケットソートすると、32階層のバケットソートが必要になる。これは約43億個に対してのlogであり、バケットソートもまたlogのオーダーから抜け出せていないことが分かる。（2ビットずつ処理しても4ビットずつ処理しても、やはりlogは消えない）通常、各値の取りうる範囲よりも、ソートすべき配列サイズの方が小さいため、バケットソートはO("n"log"n")ソートよりも実質低速であることが多い。また、文字列に対しても、頭から1文字ずつ再帰的にバケットソートを行うことができる。32ビット整数のソートは、長さ32の1ビット文字からなる文字列をソートしているとみなすこともできる。計算量の種明かしは「バケットソートの分割統治」の項で行ったため、利点とはならない。比較を行わなわずにソートできる点は利点となる。しかしながら、その裏返しとして、ソート対象の値のモデルに合わせてプログラムを書く必要を生ずる。バケットソートのバケツをメモリ空間の代わりに時間に置き換えたものである。そのままの実装では要素の最大値の時間が経過するまで待つ必要があるので実用性はない。bashによる実装

出典:wikipedia