マージソート

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

ここまでの 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 回の比較で済みました。それぞれの列の中身がすでに並んでいるおかげで、先頭より小さい値がその列に残っていないと言い切れるからです。片方が尽きたら、残りも並んでいるので比べずに付けられます。

merged = [1, 2, 3, 4, 5, 6, 7]
left = [8]     # まだ残っている
right = []     # 尽きた
merged += left # 残りは並んでいるので、比べずに付ける
print(merged)  # [1, 2, 3, 4, 5, 6, 7, 8]

並んでいる 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 つが配列の中だけで完結していたのとは対照的です。

よくある間違い

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

演習で使う書き方

本文の二列を合流させる例を、分割した左右にも適用します。append は末尾への一要素追加です。残った列を追加する処理と配列の切り出し位置は用意します。演習では再帰の停止と左右への呼び出しに加え、結合中の比較と位置の更新も書きます。二つの関数を順に完成させてください。

1. 停止条件・左右への再帰・先頭の比較と結合を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える