マージソートは、分けたデータをどうやって並べるの？
ばらばらの数字カードを、小さな列に分けてから合流。マージソートの仕組みと、先頭だけ比べてよい理由を、二つの図でたどろう。
まず、ひとことで
マージソートは、列を小さく分けて並べ、それぞれが整った二列の先頭を比べて合流させる方法だよ。小さい方を順に選べるのは、どちらの列も、すでに同じ決まりで並んでいるからなんだ。
名前や点数を、使いやすい順番へ
図書室の本の番号が、ばらばらに並んでいたらどうだろう。読みたい一冊を探すたびに、あちこちを見ることになるね。番号の小さい順にそろっていれば、探す手がかりを使いやすくなる。コンピューターの中でも、名前や点数などを決めた順番に並べ直す仕事があるよ。これをソートという。今日は、その方法の一つ「マージソート」を、数字のカードでたどってみよう。
まず、何を比べるかを決める必要がある。点数なら点数、名前なら文字の順番、という目印だよ。この目印をキーと呼ぶんだ。今回は、カードに書いた整数そのものをキーとして、小さい順に並べる。同じデータでも、点数の高い順か低い順かで答えは変わるね。どんな順番を正解とするかを先に決めることが、並べる仕事の出発点なんだ。
一枚まで分けてから、二列を合流させる
カードが左から「4、1、3、2」と並んでいるとしよう。真ん中で「4、1」と「3、2」に分け、さらに一枚ずつに分けるよ。一枚だけの列は、並び方を直す必要がない。そこから「4」と「1」を小さい順に合わせると「1、4」、「3」と「2」を合わせると「2、3」になる。最後に、その二列を合わせて「1、2、3、4」を作るんだ。最初の図で、分ける向きと、合わせる向きを見てみよう。
二つの列を一つに合流させる操作を、マージというよ。ただし、二列とも、すでに同じ決まりで並んでいることが大切だ。「4、1」と「3、2」を、そのまま先頭だけ比べても、後ろに隠れた小さい数を見落としてしまう。マージソートは、まず小さな列の順番を整えるから、次の合流を安心して進められるんだ。分けるだけで整列が終わるわけではないんだね。
四枚のカードで示した手順の模式図。上から下へ進むよ。一枚になるまで分けた後、小さな列から順番を整えて合流する。
出典資料に基づきEggplanetが作成した模式図合流のコツは、二列の先頭だけを見ること
もう少し長い例で合流を見よう。左の列が「1、4、7」、右の列が「2、3、8」なら、先頭の1と2を比べ、小さい1を答えの列へ移す。次は、左に残った先頭の4と、右の先頭の2を比べ、2を移す。その次は4と3を比べるから、3が続く。答えは、少しずつ「1、2、3……」と伸びていくよ。移した側だけ、先頭が次のカードへ進むんだ。
どうして、列の奥まで毎回探さなくてよいのだろう。それぞれの列は小さい順だから、残ったカードの中で一番小さいものは、その列の先頭にある。だから、二つの先頭のうち小さい方は、残り全部の中でも一番小さい。これを繰り返すと、答えも小さい順に伸びるんだ。一方の列が空になったら、もう一方の残りを順番どおり後ろにつなげばよい。残りの列も、すでに整っているからだよ。
同じ仕事を、小さな問題にも頼む
四枚より多いカードでも、考え方は同じだよ。列をだいたい半分に分け、それぞれの半分を並べ、二つをマージする。その「半分を並べる」仕事でも、また半分に分ける。同じ手順を、より小さな問題に使う考え方を再帰と呼ぶんだ。ただし、一枚以下になったら分けるのをやめる、という終わりの条件が必要だよ。いつまでも同じ大きさの問題を頼み続ける仕組みではないんだ。
二つ目の図は、先頭の比較を追いかける合流の記録だよ。全体を分ける図と、合流の一回を詳しく見る図は、見ている大きさが違う。実際のプログラムでも、小さな部分が正しく働くかと、それを組み合わせた全体が正しいかを分けて考えられる。二分探索も半分を使うけれど、探す範囲を絞る仕事だね。マージソートは両方の半分を並べ、カードを全部答えへ戻すんだ。
すでに小さい順の二列を使った例。各行は一枚を答えへ移した記録。最後は左が空になるので、右に残った8を後ろにつなぐ。
出典資料に基づきEggplanetが作成した模式図数が増えたときは、合流の段に注目
八枚を半分ずつに分けると、八枚、四枚、二枚、一枚と、小さな問題になっていく。一枚の列から戻るときは、二枚の列を作る段、四枚の列を作る段、八枚の列を作る段の三段で合流するよ。十六枚なら、合流は四段になる。カードの数を二倍にしても、段の数は一つ増えるだけなんだ。これは、ここで選んだ八枚と十六枚のように、きれいに半分にできる枚数で見た例だよ。
一つの段では、別々の組で合流していても、合わせて全カードを順に扱う程度の仕事になる。枚数をnと書くと、段の数が増えるゆっくりした速さはlog nで表せる。よく「n log nの手間」と説明するのは、各段の仕事と段数を組み合わせるからだよ。これは、処理時間が何秒かをそのまま答える式ではない。機械や書き方にも左右されるけれど、数が増えたときの増え方を比べる目印になるんだ。
同じ点数なら、先にいた人を先へ
数字が同じカードにも、違う名前が書いてある場合を考えよう。先に並んでいたアオさんも、後ろのミドリさんも五点だったとする。点数だけで並べるなら、どちらが先でも五点のまとまりにはなるね。でも、同点の人同士で元の順番を保ちたいこともある。この性質を「安定」と呼ぶよ。毎回同じ結果になる、という意味だけではなく、等しいキーの順番に注目した言葉なんだ。
元の列を前半と後半に分け、両方が安定に整っているとしよう。合流で同点になったとき、前半側の先頭を先に選べば、元は前にいた人を先へ残せる。その決まりを小さな合流でも守れば、全体も安定に並べられるよ。ここでの「前半側を優先」は、分ける前の順番に理由がある。いつでも好きな側を選んでよいという話ではないんだ。数字の順だけでなく、同点の扱いまで決まりに含められるんだね。
並べる速さのほかに、作業場所も考える
カードをマージするとき、机に答えの列を作る場所があると分かりやすいね。基本的な配列のマージソートも、合流のための別の作業領域を使う方法がある。速さを考えるだけでなく、どのくらい記憶する場所が必要かも大切なんだ。作業領域の使い方が違う工夫もあるから、マージソートなら全て同じ量の場所を使う、と決めつけることはできないよ。
また、実際のソフトウェアでは、すでに並んだ部分を活用するなど、いくつかの工夫を組み合わせることがある。たとえばPythonの公式資料は、組み込みのソートがTimsortという方法を使うと説明しているよ。今回の四枚の手順が、そのまま全ての機械の中で動いている、という意味ではないんだ。まず基本の仕組みを知ると、速さや安定性、記憶場所を工夫する理由が見えてくるね。
どっとと考えよう：同点カードも合流できる？
紙に「3・アオ」「1・キイロ」「3・ミドリ」「2・モモ」と書いた四枚を用意しよう。色の名前は人を見分けるためで、比べるのは数字だけだよ。最初の二枚と後の二枚を、それぞれ小さい順に並べてから合流してみてね。先頭が同じ数字なら前半側を先に選ぶ。最後に、アオとミドリの前後関係が、最初と同じになっているか確かめよう。
次は、一方の列だけを大きい順にして、同じ合流を試したらどうなるか、紙で予想してみよう。先頭が、その列の一番小さい数ではなくなるから、うまくいくという理由が崩れるね。手順を覚えるだけでなく、「どんな条件なら正しいのか」を言葉にしてみるのが大事なんだ。二列が同じ決まりで整っていることが、先頭だけ比べて並べられる秘密だよ。
ことばのメモ
- ソート
- データを、決めた順番に並べ直すこと。
- キー
- 並べるときに比べる目印。点数や名前などを選ぶよ。
- マージ
- すでに同じ決まりで並んだ列を、一つの並んだ列に合流させること。
- 再帰
- 同じ手順を、より小さな問題にも使う考え方。終わりの条件が必要だよ。
- 安定なソート
- キーが等しいデータ同士では、元の前後関係を保つ並べ方。
- 作業領域
- 処理の途中のデータなどを、一時的に置く記憶場所。
もとになった資料・もっと知りたい人へ
下記の資料をもとに、説明と考える問題を独自に構成しています。外部資料には英語のページもあります。どっとの画像は案内用のイラストで、観測写真や科学的な図ではありません。
- NIST：merge sort（分割・再帰・マージと計算量）
- NIST：merge（すでに並んだ列を合流させる定義）
- Cornell大学 CS2110：Lecture 7 Sorting Algorithms（合流の実装・安定性・作業領域）
- Python公式：Sorting HOWTO（キー・安定性・Timsort）
分かりやすくするために、説明を短くしたり、たとえ話を使ったりしています。まちがいを見つけたらお問い合わせへお寄せください。制作方法は編集方針、いっしょに読むときのヒントは保護者・先生へで紹介しています。