バケットソート
仮に32ビット整数をソートする場合に、約43億個のバケツを持つことは非現実的である。 バケツは1つの値に対して1つのバケツを用意する必要はなく、範囲を持ったバケツが矛盾なくソートされていれば良い。 この時、各バケツの中身は別ソートアルゴリズムでソートしてやるか、再度バケットソートを適用する必要がある。
冒頭の32ビット整数を1ビットずつ再帰的にバケットソートすると、32階層のバケットソートが必要になる。 これは約43億個に対してのlogであり、バケットソートもまたlogのオーダーから抜け出せていないことが分かる。 (2ビットずつ処理しても4ビットずつ処理しても、やはりlogは消えない。)
通常、各値の取りうる範囲よりも、ソートすべき配列サイズの方が小さいため、バケットソートはO(nlogn)ソートよりも実質低速であることが多い。
また、文字列に対しても、頭から1文字ずつ再帰的にバケットソートを行うことができる。 32ビット整数のソートは、長さ32の1ビット文字からなる文字列をソートしているとみなすこともできる。