ここでは、Haskellでマージソート(merge sort)を実装してみましょう。 マージソートを知らない人は このページ を参照してください。 Haskell によるマージソートの実装は以下のようになります。 なお、この実装によるマージソートは安定ソートです。
マージソートを素朴に実装すれば上記のようになりますが、 splitAt 関数で系列を２分していく部分の効率がよくありません。 リストの分割には \(O(n)\) の計算量がかかるからです。 しかし、多少直感的ではなくなりますが、 以下のようにすると splitAt を消去することができます。 この実装によるマージソートも安定ソートです。
msortN 関数で、単にソートした系列を返すのではなく、 指定された長さ分だけ処理した後、 ソート済みの系列とまだ処理されていない未ソートの系列の組を返します。 こうすると、msortN 関数の前半部分の処理で半分だけリストをかじり、 後半部分で残りのリストをかじるという風に処理を進めることができます。 このようなテクニックをタプリングと呼ぶそうです。 ただし、マルチスレッドで並列化しようとする場合、 この方法は後半の処理が前半の処理に依存するのでうまくいきません。 これ以外にも、splitAt を消去する方法として ボトムアップマージソート があります。
ところで、msortN 関数の再帰の終了条件が msortN 0 xs と msort N 1 xs ではなく、msortN 1 xs と msortN 2 xs になっているのが不思議な人もいるかもしれません。 こうすると記述は少し複雑になりますが、その分高速に動作します。