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