ここでは、Haskellでコムソート(comb sort)を実装してみましょう。 コムソートを知らない人は このページ を参照してください。 とりあえず計算量を無視して実装すると以下のようになります。
しかし、これはとてつもなく遅いです。 リスト cs は先頭から要素を取り出し末尾に要素を追加する必要があるので、 cs ++ [x] のような式を書かねばなりません。これは \(O(n)\) の計算量がかかり、 コムソート全体では \(O(n^2\log n)\) の計算量になってしまいます。 先頭はいじらず cs の末尾に追加するだけなら、(:) 演算子でつないで最後に reverse するという方法で誤摩化せるのですが、 両端をアクセスする必要がありそうもいきません。
そこで、cs をリストではなく Haskell が提供しているキューに置き換えてみましょう。 キューを使うには Data.Sequence を import します。 キューの左から要素を取り出すにはキューに viewl 関数を施して (:<) 演算子にパターンマッチします。キューの右に要素を追加するには (|>) 演算子を使います。
キューは先頭からの要素の取り出しも末尾への要素の追加も \(O(1)\) の計算量で行えますので、それを用いたコムソートは通常の \(O(n\log n)\) の計算量になります。
さて、これで一応計算量 \(O(n\log n)\) のコムソートはできましたが、 できればリストだけで実装したいという、 リスト原理主義者の人もいるかもしれません。 多少工夫すればそれも可能です。リストを使った計算量 \(O(n\log n)\) のコムソートの実装は以下のようになります。
こちらのコードの方が、キューを使うより速くなります。