はじめに
この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の４日目の記事です。
マージソートとは
Dさんが所属する４０人クラスには８人１組の班がある。班長は毎日、班員のノートを回収し、出席番号順に並べ変えた上で担任の先生に提出しなければならない。班長であるDさんは班員のノートをすべて回収した。そしてノートを出席番号順に並び替えようとしたところで、Dさんは情報の授業で習ったマージソートを思い出したので、これを用いて８冊のノートを並び替えようとした。
Dさんはまず、８冊のノートの山を４冊ずつ２つの山に分けた。次に、それぞれの山をさらに半分に分け、最終的に１冊ずつの山（？）にした。１冊だけの山は既に出席番号順に並んでいると見なすことができる。Dさんは、２つの山の１番上にあるノート同士の出席番号を比べ、小さい方を先に重ねることで中くらいの山を作った。残りの小さな山も同様にして、中くらいの山がいくつかできた。そして、今度は中くらいの２つの山の一番上同士を比較して小さいノートを山の上に置いていき、出席番号順に並んだ大きな山をいくつか作った。
この操作を繰り返してノートを並び替えたDさんは、先生にノートの山を提出して家に帰った。
マージソートを書いてみる
翌日、また班員のノートを並び替えていたDさんは、毎日同じ作業をするのを大変に感じ、マージソートをアルゴリズムとして図１にまとめた。
yama ← {34, 13, 8, 22, 33, 12, 32, 29}
satsusu ← 8
yama ← merge_sort(yama, 1, satsusu)
関数 merge_sort(A, left, right)を
| もし left < right ならば
| | mid ← (left + right) ÷ 2
| | A ← merge_sort(A, left, mid)
| | A ← merge_sort(A, mid + 1, right)
| | A ← merge(A, left, mid, right)
| を実行する
| Aを返す
と定義する
関数 merge(A, left, mid, right)
| L ← A の left から mid までの要素のコピー
| R ← A の mid + 1 から right までの要素のコピー
| L の末尾に 十分に大きな値（番兵）を追加
| R の末尾に 十分に大きな値（番兵）を追加
| i ← 1
| j ← 1
| k を left から right まで 1 ずつ増やしながら、
| | もし L[i] <= R[j] ならば
| | | A[k] ← L[i]
| | | i ← i + 1
| | を実行し、そうでなければ
| | | A[k] ← R[j]
| | | j ← j + 1
| | を実行する
| を繰り返す
| Aを返す
と定義する
図１のアルゴリズムを使ってノートを並べ替えたDさんは、ノートを先生に提出して家に帰った。
マージソートの計算量について
次の日、Dさんは先生に学年全員のノートを並べ替えるように言われた。Dさんの学年は３００人いるので３００冊のノートを並べ替えることになる。Dさんは最悪で何回並べ替えるのかを見積もった。（以下で対数の底は２とする。）
まずN冊のノートの山を２分していくので、logN段階で小さな山ができる。そして、山同士を合わせるときに、山のすべてのノートの出席番号を比較するので小さな山を２つずつ合わせていくと全部でN回比較することになる。これで小さい山から中くらいの山になった。中くらいの山同士を合わせるときにも各山のノートを一通り比較するのでN回比較する。山を合わせるのは全部でlogN回なので、全体としておよそ N × logN 回比較する必要がある。以前、情報の授業中に習った選択ソートで並べ替えるにはおよそN2回かかるので、マージソートはいいなぁと思ったDさんであった。