最初にソースコードを示します。importで、ちょっと変なことをしていますが、これはstream-fusionパッケージのリストインタフェースを使うためのおまじないです。Preludeから隠す名前を明示するのでも良いのですが、ここでは使う名前のみをインポートすることにしました。Data.List.Streamが、stream-fusionの提供するリストインタフェースで、foldrなどを使って書かれている関数に現れているパターンが融合変換可能であれば融合変換してくれます(されるはずです)。split_to_monotonesは、入力のリストを非減少列リストのリストに変換します(バラバラにしても良いのですが、そうすると入力がほぼソートされている場合でも計算量が同じになります)。foldrを2回使っていますが、このようにfoldrに渡す関数の第2引数でパターンマッチを行う場合は、過剰なstrictnessが発生しないよう注意する必要があります。一見するとパターンが尽くされていないので(-Wallを指定していた場合に)Warningが出そうに見えますが、遅延パターンは反駁不可なのでパターンは全て尽くされているものとみなされます(マッチしなかった場合は実行時のエラーになりますが、ここでは構造的にどんな入力に対しても必ずマッチします)。x」というOrd関係が定義されているので、生成する列を非増加列にするか、あるいは大小関係が逆のMaybeを作るなどすればgが少し単純になりますが、そのままにしています。続いてマージソート本体です。より作ったリストにつなげています。...)というように、mergeの出力がどんどん入力に追加されていく、という感じになるわけです。マージソートは安定ソートになっている実装もありますが、この実装では安定ではありません。6]のマージで前後が逆転しています。以上のようにしてマージが進むわけですが、マージし終わった場合の停止と結果の取り出しが問題です。純粋でない言語であれば、マージしようとしている2個のリストが同一のオブジェクトであれば(内容が同じオブジェクトは共通化される、という最適化は無いものとして)止まれば良いわけですが、Haskellではそういうわけにはいきません。ここでよく考えると、必ず「2個のリストが1個になる」というステップでソートが進むわけですから、最初のリストの長さに応じて、必ず一定数個のリストをたぐれば答えが得られるわけです。lst_lst」という式というわけです。全体的に単純にするために、loopの先頭に1個余計な空リストを追加しています。あとはmergeの中身ですが、一見大げさですがたいしたことはしていません。再帰を明示的に書かないようにするため、このようになっています。foldrで入力のリストを振り分けて2本のリストにします。zipで2本のリストを、タプルのリストにします。mがマージ作業そのもので、見たままなので特に解説は必要ないでしょう。