マージソート

隣どうしの交換では、遠くの値が遠すぎる

ここまでの 3 つは、どれも 1 回の操作で値を 1 マスか、せいぜい数マスしか動かせませんでした。左端にいる最小値を右端から引っ張ってくるのに、比較が要素数ぶん必要になります。だから手間が要素数の 2 乗に近づきます。

発想を変えます。ばらばらの値を動かすのをやめて、すでに並んでいる 2 本の列を 1 本につなぐことを考えます。

2 本の列は、先頭だけ見比べればつながる

[3, 5, 6, 8] と [1, 2, 4, 7] があります。どちらも並んでいます。この 2 本から 1 本を作るのに、全部を見比べる必要はありません。

• 先頭は 3 と 1。小さい 1 を取る
• 3 と 2。2 を取る
• 3 と 4。3 を取る
• 5 と 4。4 を取る
• 5 と 7。5 を取る
• 6 と 7。6 を取る
• 8 と 7。7 を取る
• 右の列が尽きた。左に残った 8 をそのまま付ける

見ているのは常に、両方の先頭 1 つずつだけです。8 個を並べるのに 7 回の比較で済みました。それぞれの列の中身がすでに並んでいるおかげで、先頭より小さい値がその列に残っていないと言い切れるからです。片方が尽きたら、残りも並んでいるので比べずに付けられます。

並んでいる 2 本は、割り続ければ手に入る

「並んでいる 2 本」など最初から無い、という話になります。ここが分割統治の面白いところで、割り続ければ必ず手に入ります。要素が 1 個の列は、それだけで並んでいるからです。

[6, 3, 8, 5, 2, 7, 1, 4] なら 4 個ずつ、2 個ずつ、1 個ずつと割り、そこから戻りながらつなぎます。

段の数は、8 個なら 3 段、16 個なら 4 段と、要素数を 2 で割り続けられる回数です。各段では合計で要素数ぶんの値に触ります。だから全体の手間は「要素数 × 段数」になり、100,000 個でも 170 万回程度で終わります。同じ入力に前の 3 つを使うと 50 億回でした。

代わりに払うものもあります。つないだ結果を置く場所が要るので、元の配列と同じだけのメモリを別に確保します。前の 3 つが配列の中だけで完結していたのとは対照的です。

よくある間違い

つなぎ終わったつもりで、残ったほうを付け忘れることです。比べる作業は片方が尽きた時点で止まるので、その後にもう一方の残りを足さないと、要素が静かに消えます。出力の長さが入力より短くなっていたら、まずここを疑ってください。

1. 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
2. 配列を半分に分割して再帰し、ソート済みの 2 列をマージする分割統治法で実装する
3. 戻り値は新しい配列で、入力 arr を破壊的に書き換えない