バケットソート
整列したいデータの取りうる値がm種類であるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づける。元のデータ列を走査して、各データを対応するバケツに入れていく。この処理が終わった後、整列したい順序に従ってバケツから値を取り出せば、データをソートすることができる。
安定ソートを実現するためには、同じバケツに入っているデータは入れたときと同じ順序で取り出す必要がある。順序が保存されない場合は、ソートはできるが、安定ソートではなくなる。後述するように基数ソートと組み合わせて使うためには、安定ソートになっている必要がある。