私のホームページを見てくれた人のツイッターで、Haskell では、 マージソートはボトムアップの方が速いという指摘があるのを見つけました。 C++ などはボトムアップなマージソートにすると 普通のマージソート より遅くなるので調べていなかったのですが、せっかくのご指摘なので、 ボトムアップなマージソートも実装してみました。なるほど、 確かに速かったです。
Haskell によるボトムアップなマージソートの実装は以下のようになります。 なお、この実装によるボトムアップなマージソートは安定ソートです。
ボトムアップなマージソートは、
まず最初に与えられた系列を昇順にソートされた区間の列に分割します。
もちろん、任意の系列には降順の部分もあるので、
そのままでは昇順の区間に分割できません。
そこで降順の部分は順序を反転して昇順に修正します。上記コードの
groupRun がそれを行う関数です。
groupRun に系列 [3,1,4,1,5,9,2,6,5,3,5,8,9]
を与えると、[[1,3],[1,4],[5,9],[2,6],[3,5],[5,8,9]]
のような昇順区間の列を返します。後は、unify
で隣接する区間のマージを繰り返し、
最終的に１つの区間にマージしてソート終了です。
関数 cutLE で、ちょっと面白いテクニックとして、
リストの末尾への要素の追加の計算量を
\(O(1)\) に抑えるテクニックが使われています。
リストの先頭への要素の追加は、以下のように計算量 \(O(1)\) ですが、
リストの末尾への要素の追加は、普通、以下のように計算量 \(O(n)\) です。
先頭への追加 [1] ==> 2:[1] ==> 3:[2,1] ==> 4:[3,2,1]
末尾への追加 [1] ==> [1] ++ [2] ==> [1,2] ++ [3] ==> [1,2,3] ++ [4]
しかし、関数の合成を利用すると、以下のように末尾への要素の追加を、 ならし計算量(amortized complexity)で \(O(1)\) にできます。
(1:) ==> (1:) . (2:) ==> (1:) . (2:) . (3:) ==> (1:) . (2:) . (3:) . (4:)
もちろん、関数は最終的にはリストに変換してやる必要があります。 この瞬間、\(O(n)\) の計算量が発生しますが、 \(n\) 個の要素で平均すれば、\(O(1)\) です。 以下のようにします。
let fs = (1:) . (2:) . (3:) . (4:) in fs [] -- [1,2,3,4] になる
この実装は、昇順および降順にソート済みの系列に対して非常に高速です。 また、小さいサイズの系列に対しても高速です。しかも安定なソートですから、 ある意味 Haskell におけるソートの決定版と言えるかもしれません。
ところで、単にマージソートしたいだけなら、
上記のコードはもっと簡単に出来ることにお気づきでしょうか？何も
groupRun で昇順区間を切り出してやる必要はなく、
map (\x -> [x])
で１つ１つ切り出してやればマージソート出来ます。
長さが１の系列は常に昇順あるいは降順と見なせるからです。
そのように書き直すと以下のようになります。
このコード、速度は MergeSort3.hs に劣りますが、 ボトムアップではない 普通のマージソート (MergeSort1.hs)には勝ります(乱数列で比較)。 何より簡単なので、憶えておきやすいですよね。 筆者はこの簡単バージョンがお気に入りです。