読者です 読者をやめる 読者になる 読者になる

マージソート解説

最初にソースコードを示します。

まず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がマージ作業そのもので、見たままなので特に解説は必要ないでしょう。