分けて、たばねる
66回の正体
前のレッスンで、差しこんでならべる手順は、逆順の12枚という最悪で66回かかりました。原因をひとことで言えば、毎回ぜんぶずらすからです。いちばん小さい札がいちばん奥から来るたびに、そろえた札を全員、1つずつ右へ動かすことになります。
ずらす作業を減らそうと、差しこみ方をいくら磨いても、この壁は消えません。発想を変えます。ならべる前に、分けるのです。
作戦：半分に分けることを、くりかえす
札の山を、半分に分けます。分けた山を、また半分に。これをくりかえすと、いつか全部の山が1枚になります。
ここで、レッスン1の最初の場面を思い出してください——「左はしの1枚は、それだけで『そろっている』」。同じことが、いま全部の山に言えます。1枚の山は、もうそろっているのです。
あとは、そろった山どうしを2つずつたばねて、大きなそろった山に戻していきます。たばねることを英語でマージ（merge）と言い、この手順はマージソートと呼ばれます。
たばねる、という速い作業
そろった2つの列をたばねる手順は、こうです。先頭どうしをくらべて、小さい方を取る。取ったら、その列の次の札が新しい先頭になるので、また先頭どうしをくらべる——これのくりかえしです。
なぜ先頭だけ見ればよいのでしょう。そろった列の先頭は、その列でいちばん小さい札だと、くらべなくても分かっているからです。だから「2つの列ぜんぶの中でいちばん小さい札」の候補は、先頭の2枚しかありません。
年賀状の束で言えば、五十音順にそろった2つの束を1つにまとめる作業です。どちらも上の1枚だけ見て、早い方を取っていけば、まとめた束も五十音順になります。ただしこのたとえでは「半分に分けるところから始める」という前半が抜けているので、作戦の後半だけのたとえだと思ってください。
実験室で見る
6つの数で、ぜんぶの流れを再生してみてください。うすく光る範囲が、いま作業中の区間です。
ならべる前。まず半分に分けることをくりかえす
前半は分ける段階なので静かに進み、たばねる場面から「先頭どうし」のくらべ合いが始まります。最後は、そろった（2,5,8）と（1,3,9）をたばねて決着です。
くらべた回数は11回でした。実は同じ6つの数を、レッスン1の差しこみは10回でならべています。山が小さいうちは、マージソートはえらくないのです。
並走対決：逆順の12枚
では、山が育って、しかも最悪の逆順だったら。差しこみが66回かかった、あの12枚で並走させます。
ならべる前。左はしの1枚は、それだけで「そろっている」
ならべる前。まず半分に分けることをくりかえす
差しこみが66回、マージソートは20回。3倍以上の差がつきました。差しこみの回数は枚数が増えると4倍ずつの勢いでふくらみますが、マージソートのふくらみ方はずっとおだやかです——どれくらいおだやかかは、次のレッスンで「かたち」として描きます。
再帰との、再会
ところで、この手順の説明を縮めると、こうなります。「半分に分けて、それぞれを同じやり方でならべて、たばねる」。
この「同じやり方で」に、聞き覚えはないでしょうか。手順の中で、手順そのものをもう一度使う——コース2のレッスン10で出会った再帰です。あのとき fact や fib が「自分の定義の中で自分を呼ぶ」のを見た人にとって、マージソートはその友だちです。コース2をまだ歩いていない人は、「自分自身を呼ぶ書き方がある」とだけ覚えておけば、ここでは足ります。
再帰には、下りていく道の行き止まり——土台が要るのでした。マージソートの土台は「1枚になったら、もうそろっている」です。だからこの手順は、永遠に分けつづけたりせず、必ず終わります。
⟡ よりみち：1945年生まれ
マージソートを考えたのは、数学者のジョン・フォン・ノイマンだと伝えられています。1945年、最初期のコンピュータの設計とほぼ同時でした。機械が生まれた瞬間から、「どんな手順で動かすか」が発明の主戦場だったわけです。
正直なコスト
ただし、マージソートはただでは速くなっていません。たばねるとき、2つの列をいったん控えの紙に書き写してから、元の場所へ戻していきます。つまり、ならべる札とは別の置き場が要るのです。
差しこみは、その場でずらすだけで、控えの紙を使いません。マージソートの速さは、置き場代で買っている——速さと置き場のどちらを取るかは、状況しだいの取引（トレードオフ）です。さっき見た「山が小さいうちは差しこみが勝つ」ことも合わせると、どちらの手順にも出番があると分かります。
✎ 演習：手でたばねて、回数をかぞえる
そろった2つの列（2,5,8）と（1,3,9）を、紙の上で手でたばねてください。「先頭どうしをくらべて、小さい方を取る」をくりかえし、くらべた回数をかぞえます。終わったら、上の実験室の最後のたばねる場面を再生して、答え合わせをしてください。
ヒント1（考え方）
最初の先頭どうしは 2 と 1 です。1 を取ったら、右の列の先頭は 3 に変わるので、次は 2 と 3 をくらべます。「くらべた回数」と「取った枚数」は同じではないことに注意してください。
こたえ
2と1、2と3、5と3、5と9、8と9——で5回です。6枚たばねたのに、くらべたのは5回でした。最後の 9 は、相手の列が尽きていたので、くらべずにそのまま置けます。片方が尽きたら残りは無条件で移せる——これも、列がそろっているおかげです。
このレッスンで分かったこと
- 差しこみの最悪66回の正体は「毎回ぜんぶずらす」。発想を変えて、ならべる前に分ける
- マージソート：半分に分けることをくりかえし、1枚になったら（＝そろっている）、そろった列どうしをたばねる
- たばねるが速いのは、そろった列の先頭は、その列の最小だと分かっているから
- 逆順の12枚で、差しこみ66回に対しマージソートは20回。ただし山が小さいうちは差がない（6枚では11回対10回で負けることも）
- 「それぞれを同じやり方で」は再帰そのもの。土台は「1枚はそろっている」
- マージソートは控えの紙（別の置き場）が要る。速さは置き場代で買っている——トレードオフ