2本の連をマージする
「1 8 9|0 2 5 7」をマージしてみましょう。まず、連の区切り|を境に2つに切りわけます:
連1: 1 8 9 連2: 0 2 5 7
次に双方の連の先頭を比べ、より小さい方を取り出します。双方の先頭は1と0ですから連2から0を取り出します:
連1: 1 8 9 連2: 2 5 7 取り出された列: 0
同じことをどちらかの連が空になるまで繰り返します:
連1: 8 9 連2: 2 5 7 取り出された列: 0 1 連1: 8 9 連2: 5 7 取り出された列: 0 1 2 連1: 8 9 連2: 7 取り出された列: 0 1 2 5 連1: 8 9 連2: 取り出された列: 0 1 2 5 7
どちらかが空になったら、残った連をすべて取り出します:
連1: 連2: 取り出された列: 0 1 2 5 7 8 9
これでマージ完了、取り出された列は昇順になってますから2本の連を1本にマージすることができました。
この一連の処理で、2つの連の先頭のみを比較していることに注目してください。任意のn番目を参照することはなく、常に先頭のみです。
ということはこの2つの連がファイル上にあったとき、“ファイルから次のデータを読む”操作があればよいことになります。取り出された列についても“ファイルにデータを一つ書く”を行うだけです。一連のマージ処理に必要なメモリ量はそれぞれの先頭データを読み込めるだけの領域さえあれば十分です。連の含むデータ量がどれほど多くても関係ありません。
分割と併合
2本の連をマージする手順は先に述べたとおりです。これを実際の処理に適用しましょう。
ソートする対象は多数の連がつながった一本のデータ列「8|1 9|2|0 5 7|3 4 6」になっていますから、まずそれを2本に分割します。
入力ファイル（in）と2本の出力ファイル（out1,out2）をオープンし、inから読んでout1に書き出します。これを繰り返し、連の切れ目に達した（前回読み込んだ値より小さかった）ならば出力先をout1からout2、あるいはout2からout1に切り替えます。
入力ファイルを読みつくしたとき、out1,out2はそれぞれ:
in: 8|1 9|2|0 5 7|3 4 6 out1: 8|2|3 4 6 out2: 1 9|0 5 7
ここまでが分割フェーズです。分割フェーズにおいても必要なメモリ領域はinから読みこむデータ一つ分で十分です。
つぎに併合フェーズ。出来上がった2本のファイルを入力（in1,in2）とし、出力ファイル（out）をオープンします。
in1: 8|2|3 4 6 in2: 1 9|0 5 7
in1,in2それぞれの連に対して前章で説明したマージ処理を行います。
in1: 2|3 4 6 in2: 0 5 7 out: 1 8 9
どちらかの入力を読みつくすまでこの処理をくりかえし、
in1: 3 4 6 in2: out: 1 8 9|0 2 5 7
最後に残った入力ファイルのデータを出力に吐き出します。
in1: in2: out: 1 8 9|0 2 5 7|3 4 6
分割と併合を施すことで、連の数がおよそ半分になった新たなファイルが作られました。これを入力として再度分割/併合を行うと:
1 8 9|0 2 5 7|3 4 6 → 0 1 2 5 7 8 9|3 4 6
連の数が1になるまで分割/併合をくりかえせばソートが完了します。
0 1 2 5 7 8 9|3 4 6 → 0 1 2 3 4 5 6 7 8 9（完了!）
分割/併合の2つのフェーズでは、いずれも全データを読み出して新たなファイルに書き込む作業ですから、各フェーズに要する時間計算量はデータ数Nに比例、すなわちΟ(N)となります。そしてこの分割/併合フェースによって連の数が半分になるのですから、分割/併合の繰り返し回数はlogN。従って、マージソートの時間計算量はΟ(N・logN)となります。
