バケットソート

バケットソート（bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、分布数えソート、計数ソート、ビンソート（bin sort）などともいう。オーダーはO(n)と高速だが、一般的なソートとは異なり、ソート対象が全順序というだけではなく「取りうる値がm種類である」というような、より強い制限を前提としている非比較ソートに分類される一つである（あるいは事前にスキャンして分布を調べるなど、モディファイを追加する必要がある）。