Version 13.18
一番便利・マージソート

「今回は、最後のソート、マージソートについて説明します」
『最後？』
「ソートのアルゴリズムは他にもいっぱいあるんだけど、基本的にはクイッ
クソートとマージソートが使えれば問題ないから」
『クイックソートとマージソート……あ、マージソートは安定ソートなん
だ！』
「そういうこと。 int とかの配列のソートはクイックソートで、構造体や
クラスの配列のソートはマージソートで、っていうのが基本かな」
『でも、マージソートってクイックソートより遅いんでしょ？』
「そんなに遅くないし、場合によってはクイックソートよりも速いよ」
『え、そうなの？』
「クイックソートは左右を入れ替えていくソートだから、元々ある程度きれ
いに並んでいる配列をソートするには向かないんだけど、マージソートはむ
しろ並んでいる方が速くソートできるから」
『そういう場合にはマージソートの方が速いわけね』
「そういうこと。だから、場合によっては全部マージソートでもいいかも
ね」
『でもクイックソートはランタイムにあるから便利……』
「確かに……さて、それではマージソートの仕組みについて説明します。
マージソートは、次のような手順でソートします」

1.全部バラバラにする。
2.隣同士をくっつける。そのとき小さい順にくっつける。
3. 2 を繰り返して、全部ひとつになるまで続ける。

『……これだけ？』
「そう。仕組み的にはクイックソートより簡単だと思うよ。ちなみに、この
処理の中の〈くっつける〉ことを merge って言います」
『だからマージソート、ね』
「そういうこと。じゃ、実際に手順を追ってみようか」

4 9 3 5 8 

『前のと同じのね』
「これをソートします。まず、全部バラバラにします」

4     9     3     5     8 

「次に、隣同士をマージします」
『マージする、つまりくっつけるのね』
「その際、小さい方は左側にします」

(4,9) 3 (5,8)

『む、なんかそのままね』
「たまたま左右そう並んでるからね。
『あと真ん中の 3 があぶれちゃったけど』
「これは次にマージするから、今は放っておきます。では、その次の段階」

(3,4,9) (5,8)

「 (4,9) と 3 をマージしました。 (5,8)は隣がないので放っておきます」
『 3 が一番左に来てるね』
「小さい方を左に持ってくるからね。では最後に、このふたつをマージしま
す」

(3,4,5,8,9)

「はい、ソートできました」
『……』
「う、何怖い顔で」
『……簡単すぎ！　なんかだましてるでしょ！』
「騙してるわけじゃなくて……タネというか、ポイントは、くっつけると
ころ、つまりマージ。たとえば」

(3,4,9)
(5,8)

「このふたつをくっつける場合」
『そうよ、これ、くっつけるって言ったけど、大変じゃないの？　小さい順
なんだから』
「ところがそうでもないんです。なぜかというと」

(3,4,9)

「も」

(5,8)

「も、すでに小さい順にソート済みだから」
『小さい順に並んでいると……簡単？』
「簡単なんです。この手順も追ってみようか」

(3,4,9)
(5,8)
　↓
[,,,,]

「という形でマージしていきます。まず１回目。この中から一番小さい数
は？」
『 3 。あ……そっか、もうこのふたつ、ソートされてるから、一番小さな
数が絶対に一番左に来てるんだ……』
「そういうこと。それがポイントなんです。一番小さな数は、 3 と 5 を比
較して、 3 」

(4,9)
(5,8)
　↓
[3,,,,]

「次に小さな数は、 4 と 5 を比較して 4 」

(9)
(5,8)
　↓
[3,4,,,]

「と、常に一番左にある〈一番小さな数〉のふたつを比較するだけでいいん
です」
『ソートの時は全部見ていかなきゃいけなかったけど、ソート済みだとそれ
が必要ない、ってわけね』
「残りも同じように見ていきます。 9 と 5 だと 5 だから」

(9)
(8)
　↓
[3,4,5,,]

「 9 と 8 だと 8 だから」

(9)
()
　↓
[3,4,5,8,]

「そして残った 9 」

()
()
　↓
[3,4,5,8,9]

『マージが終わったら、もうそのときソートもされてるわけね……』
「マージソートの早い理由はこれ。常にソート済みにしておくことで、全体
を見る、という処理をしないで済むわけです」
『これは早そう……』
「それに、このソートは左右をそのまま残しておくから」
『安定ソート！』
「ってわけ」
『元々の位置はそのままだものね』
「そう、それも重要」
『？』
「ごちゃごちゃにかき混ぜるクイックソートに比べて、マージソートはその
ままの並び順をうまく活用するから、〈元々ある程度ソートされてる〉場合
にかなり早くソートできるんです」
『マージがそのままできるもんね』
「こういったメリットがあるから、クイックソートは必要ないかも」
『マージソートのデメリットは？』
「メモリを多く使うこと。今まで紹介したソートは元々の配列を利用してい
たけど、今回はそうできないんです」
『どして？』
「マージの時に別の領域が必要になるから」

(3,4,9)
(5,8)
　↓
[,,,,]

『あ”』
「まぁプログラム的には上の () の領域を作ることになるんだけど」
『分割した方ってこと？』
「そう。分割した値を動的に作った配列に入れておいて、マージするときに
元の配列に戻していく、っていう形になります」
『動的に作る、ってことは、 malloc() とか new とか使うってこと？　め
んどくさそう……』
「確かにそうかも。でもこれも、一度作っちゃえば使い回しできるから、そ
れほど大変じゃないと思うよ」
『……なんか、マージソートができればもう他には必要ないように聞こえる
けど』
「実際そうだと思うよ。マージソートの関数をちゃんと作っておけば、もう
それだけで十分かも」

/*
    Preview Next Story!
*/
『仕組みがわかったらコーディング、ね』
「というわけで次回はマージソートのコードを紹介します」
『……あらかじめ訊くけど』
「ランタイムはないよ」
『うー』
「というわけで次回」
＜ Version 13.19 マージソートのコーディング ＞
『につづく！』
「まぁ他の言語だとあらかじめ用意されてたりするんだけどね」
『え！？　じゃあそっちに乗り換えるー！！』
「じゃあ #pragma twice が最終回になったらね」
『え”……』