バケットソートは計算量が \(O(n)\) と非常に高速ですが、 ソートするキーの定義域が十分に小さい整数区間でないとソート困難です。 これはかなり厳しい制限でしょう。一般に、 比較ソートの計算量は \(O(n\log n)\) より小さくならないことが知られていて、 バケットソートのような制限を設けないと \(O(n)\) のような計算量は実現できません。
比較ソートというのは、 ソートする系列の要素に全順序関係以外の制限を設けないソートのことです。 クイックソート や マージソート は比較ソートですが、 バケットソートは比較ソートではありません。
しかし、何とかして比較ソートのままで計算量 \(O(n)\) が実現できないものでしょうか？実は、そんな方法があります。 キーの定義域が十分に小さい整数区間であるなどという制限はなく、 比較のみで \(O(n)\) が実現できるソート、 それがツリーソート(２分木ソート, tree sort)です。 しかも、安定ソートです。
えー！そんなバカな、と思うでしょう。はい、 もちろん手品には種があります。全順序関係であれば良いのですが、 計算量を \(O(n)\) に抑えたかったら要素の種類が十分に少ないという条件もクリアしないといけません。要素の数は多くてもかまいません。ですから、 まあ、性能を出そうと思ったら比較ソートではなくなるんですね。 でも \(O(n)\) にこだわらなければ比較ソートですよ。 バケットソートが、 キーの定義域にあらかじめ決められた整数の小さな区間が必要なのに対して、 ツリーソートは定義域が無限の実数の系列だろうが文字列の系列だろうがソートできます。
それでは、Haskellでツリーソートを実装してみましょう。 C++ による実装をお望みの方は こちらのページ へどうぞ。
するどい人はもう気づいたと思いますが、 ツリーソートはバケットソートの変種です。 バケツを２分探索木に配置するようにしただけです。ですから、 要素の種類が少ないと探索にかかるコストは無視できて計算量は \(O(n)\) になるというわけです。
要素の種類が多くて、 例えば要素数に比例するくらいの種類があったとしても、 与えられる系列がランダムな系列なら、 生成される２分探索木が平衡木になるので、計算量は \(O(n\log n)\) になります。問題はソート済みの系列が与えられた時で、最悪計算量は \(O(n^2)\) になります。
ツリーソートで最悪時でも計算量を \(O(n\log n)\) 程度に押さえたい場合、 次ページ以降で紹介する 赤黒木ソート や AVL木ソート、 2-3木ソート を使います。
ところで、 flatten 関数の実装が分かりにくいなぁと思った方も居るかもしれません。 コメントに書いてある通り、素朴な実装では最悪計算量が \(O(n^2)\) になるケースがあります。 それでこんな分かりにくい実装になっているわけです。
このあたりに、 関数型プログラミング言語の限界というか問題があるような気がします。 多くの関数型言語が基本的データ構造に単方向リンクトリストを採用していますが、これの連結には \(O(n)\) の計算量がかかってしまいます。そのために上記のような問題が起こります。
しかし、手続き型プログラミング言語で、副作用を許容し、 双方向リンクトリストなど適切なデータ構造を選べば、 系列の連結は計算量を \(O(1)\) にすることができ、 上記の関数型言語のような問題は起きません。 つまり、flatten 関数を素朴な実装なままで最悪計算量 \(O(n)\) にできます。