マージソート わかりやすく

一マスずつでは遅い

前回のやり方は、単純なのがよいところでした。隣どうしを比べて、大きいものを後ろへ送ればよかったのです。
でも列が長くなると、比べることが多くなりすぎます。
カードが二倍になると、比較は四倍に跳ね上がります。四枚ならすぐですが、三十二枚になると気が遠くなります。

列を二倍にしてみます。長さ二倍 → 比較は四倍に急増。

棒がおそろしい勢いで伸びていきます。
列が長くなるほど、遅さはひどくなります。
問題は、列全体を一つのかたまりとして見て、最後まで比べることにあります。
では、かたまりを分けてみたらどうでしょう。

半分に分ける

長い列をまるごと扱うのではなく、半分に分けます。
その半分をまた半分に、さらにその半分も半分にと分け続けると、最後には一マスだけが残ります。
そして一マスは、もう並んでいるのと同じです。一人きりなので、比べる相手がいないからです。

一つの束を半分に分け続けます。8 → 4+4 → 2+2+2+2 → 一マスずつ。

分けるだけで終わりでしょうか。
いいえ。分けたものは、また集めないと列になりません。一マスのものを二つずつ組にして合わせ、その合わせたものをまた合わせます。
そして、並んだ二つを合わせるのは、意外と簡単なのです。

並んだ二つを合わせる

並んだ二つの束を一列に合わせるときの秘訣は、先頭だけを見ることです。
二つの束の最初のマスを比べ、小さいほうを結果に落とします。その場所は次のマスが埋め、また最初のマスどうしを比べます。
ファスナーを閉めるように、一マスずつかみ合わさっていきます。

二つの束の先頭を比べ、小さいほうを落とします。ファスナーのように一マスずつ合わせます。

ふしぎではありませんか。ばらばらな全体を比べるときは遅かったのに、それぞれ並んだ二つを合わせるときは先頭だけ見ればよいので速いのです。
分けたおかげで小さく並んだかけらができ、そのかけらを順々に合わせていけば、いつのまにかきちんとした列になります。

なぜ速いのか:層の数

なぜこのほうが速いのでしょうか。
半分ずつ分けるので、分ける層があまり多くなりません。列が二倍になっても、層はたった一つ増えるだけです。
一つの層を合わせる費用は列の長さくらいなので、全体の費用は層の数かける列の長さです。
一マスずつ比べるとき(長さかける長さ)より、ずっとゆっくり大きくなります。

層を広げて、列の長さを変えてみます。層の数 x 一層 = 一マスずつよりゆっくり大きくなる。

正確な式は、あとでくわしく学びます。
いまは感覚だけ持ち帰れば十分です。半分に分ければ層はなかなか増えず、それぞれの層は軽く合わさるので、全体が速くなるということ。
分けて合わせるこの一手が、速さをがらりと変えるのです。

まとめ

一本の糸につなぐと、こうなります。
一マスずつ比べる並べ替えは、列が長いほど遅くなります。
そこで列を半分に分け、最後まで分けて、もう並んでいる一マスのかけらを作ります。
その並んだ二つをファスナーのように合わせれば、層の数だけ合わせればよいので、列全体がずっと速くそろいます。
分けて合わせる、これが賢い並べ替えのかなめです。

四つの段階を順に押して、ひと回りたどります。分ける → 一マス → 合わせる → 層の数だけ = 速い。

ここでは、いつも落ち着いて半分ずつ分けました。
でも、分ける基準を少し違うふうに取るいとこもいます。真ん中ではなく、あるマスを基準にして、小さいものと大きいものに分ける方法です。
その基準をどう選ぶかは、また先の話にしておきます。
きょうは、半分に分けて合わせれば速くなる、ということだけ持ち帰ってください。