マージ（併合）
既にソートされている複数の配列やファイルを、ソートの順序を保持しつつ、一つの配列やファイルにまとめることをマージ（併合）といいます。
２つの順編成ファイル、ファイルＢとファイルＣが、それぞれコードＢとコードＣの昇順にソートされています。それをマージしてファイルＡにするアルゴリズムを考えます。
ファイルＢ ファイルＣ ファイルＡ
コードＢ コードＣ
┌──┬─────┐ ┌──┬─────┐ ┌──┬─────┐
│１０│ＢＢアアア│ │２０│ＣＣカカカ│ ①│１０│ＢＢアアア│
├──┼─────┤ ├──┼─────┤ ├──┼─────┤
│３０│ＢＢイイイ│ │４０│ＣＣキキキ│ ②│２０│ＣＣカカカ│
├──┼─────┤ ├──┼─────┤ ├──┼─────┤
│４０│ＢＢウウウ│ │６０│ＣＣククク│ ③│３０│ＢＢイイイ│
└──┴─────┘ └──┴─────┘ ├──┼─────┤
：９９：Ｂの終わり： ：９９：Ｃの終わり： ④│４０│ＢＢウウウ│
・……・……………・ ・……・……………・ ├──┼─────┤
⑤│４０│ＣＣキキキ│
├──┼─────┤
⑥│６０│ＣＣククク│
└──┴─────┘
アルゴリズム
一般的には、次のようになります。
コードＢ＜コードＣ ： ファイルＢのレコードをファイルＡにコピーして、次にファイルＢを読む
コードＢ＞コードＣ ： ファイルＣのレコードをファイルＡにコピーして、次にファイルＣを読む
コードＢ＝コードＣ ： ファイルＢとＣのレコードをファイルＡにコピーして、次にファイルＢとＣを読む
ファイルのすべてのレコードを読み終わった後をどうすればよいでしょうか。
上図の点線のようなダミーレコードがあればよいと考えられます。このような機能は、例えばＣＯＢＯＬでは
READ ファイルＢ AT END コードＢ＝大きい値．
という機能があります。
プログラム
ア ファイルＢを読む。終わりならば コードＢ＝９９;
イ ファイルＣを読む。終わりならば コードＣ＝９９;
ウ while ( (コードＢ＜９９) and (コードＣ＜９９) ) {
エ if (コードＢ＜コードＣ) {
オ レコードＢをファイルＡに出力;
カ ファイルＢを読む。終わりならば コードＢ＝９９;
キ }
ク else if (コードＢ＞コードＣ) {
ケ レコードＣをファイルＡに出力;
コ ファイルＣを読む。終わりならば コードＣ＝９９;
サ }
シ else if (コードＢ＞コードＣ) {
ス レコードＢをファイルＡに出力;
セ レコードＣをファイルＡに出力;
ソ ファイルＢを読む。終わりならば コードＢ＝９９;
タ ファイルＣを読む。終わりならば コードＢ＝９９;
チ }
ツ }
トレース
ア コードＢ＝１０
イ コードＣ＝２０
ウ コードＢ＜９９ コードＣ＜９９、 コードＢ（１０）＜コードＣ（２０） → オへ
オ コードＢ（１０）のレコードを出力 ①
カ コードＢ＝３０ → ウへ
ウ コードＢ＜９９ コードＣ＜９９、 コードＢ（３０）＞コードＣ（２０） → ケへ
ケ コードＣ（２０）のレコードを出力 ②
コ コードＣ＝４０ → ウへ
ウ コードＢ＜９９ コードＣ＜９９、 コードＢ（３０）＜コードＣ（４０） → オへ
オ コードＢ（３０）のレコードを出力 ③
カ コードＢ＝４０ → ウへ
ウ コードＢ＜９９ コードＣ＜９９、 コードＢ（４０）＝コードＣ（４０） → スへ
ス コードＢ（４０）のレコードを出力 ④
セ コードＣ（４０）のレコードを出力 ⑤
ソ ファイルＢ終わり コードＢ＝９９
タ コードＣ＝６０ → ウへ
ウ コードＢ＝９９ しかし コードＣ＜９９、 コードＢ（９９）＞コードＣ（６０） → ケへ
ケ コードＣ（６０）のレコードを出力 ⑥
コ ファイルＣ終わり コードＣ＝９９ → ウへ
ウ コードＢ＝９９ AND コードＣ＝９９ → 終了
練習問題
＜問題＞
ファイルＢとファイルＣがソートされているとの条件に反しますが、次のファイルを、上のプログラムでマージすると、どのようになるでしょうか。
ファイルＢ ファイルＣ
コードＢ コードＣ
┌──┬─────┐ ┌──┬─────┐
│１０│ＢＢアアア│ │２０│ＣＣカカカ│
├──┼─────┤ ├──┼─────┤
│４０│ＢＢイイイ│ │６０│ＣＣキキキ│
├──┼─────┤ ├──┼─────┤
│３０│ＢＢウウウ│ │５０│ＣＣククク│
└──┴─────┘ └──┴─────┘
＜解答＞
┌──┬─────┐
│１０│ＢＢアアア│
├──┼─────┤
│２０│ＣＣカカカ│
├──┼─────┤
│４０│ＢＢイイイ│
├──┼─────┤
│３０│ＢＢウウウ│
├──┼─────┤
│６０│ＣＣキキキ│
├──┼─────┤
│５０│ＣＣククク│
└──┴─────┘
かなり複雑になりますが、入力ファイルが３つ以上でのマージを行うことも可能です。その機能をもつユーティリティソフトウェアが提供されています。
外部ソート
磁気ディスクや磁気テープなど、外部記憶装置にあるファイルをソートすることを外部ソートといいます。
ファイルの全データをメモリに読み込むことは、メモリ容量が不足しますので、外部記憶装置を用いてソートする必要があります。
直接編成ファイルや索引順編成ファイルなどに関しては、別章で取り扱いますので、ここでは順編成ファイルを対象にします。
ソートするキー項目が次のように並んでいるファイルＡをソートすることを考えます（キー項目以外の項目は煩雑になるので省略します）。
ファイルＡ
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│３０│６０│９３│１４│８４│４１│７１│５３│２６│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
アルゴリズム
①～③ や ④～⑤ など、部分的には既にソートされています。ソートされている部分を連といいます。
ファイルＡを連ごとに別のファイル（ワークファイルといいます）に出力すれば、
３０、６０、９０
１４、８４
４１、７１
５３
２６
の４つのファイルになります。
この４つのファイルをマージすればソートが完成します。
複数のファイルをマージするソフトウェアがあるにせよ、せいぜい数ファイルを想定しているのであり、ワークファイルの個数が数百、数千のファイルになる場合には使えません。それで、限られたワークファイルでソートする工夫をする必要があります。ここでは、ワークファイルをファイルＢとファイルＣの２つであるとします。
- 分割
- ファイルＡのレコードを、連をファイルＢとファイルＣに交互に出力します。上の例では、
ファイルＢ：３０、６０、９０、４１、７１、２６
ファイルＣ：１４、８４、５３
となります。 - マージ
- ファイルＢとファイルＣをマージしてファイルＡに出力します。
ファイルＡ：１４、３０、６０、８４、５３、９０、４１、７１、２６
となります。
このファイルＡはソートされていません。それでまた分割とマージを行います。これを繰り返すことにより、ソートができます。
ファイルＡ：１４、３０、６０、８４、５３、９０、４１、７１、２６
ファイルＢ：１４、３０、６０、８４、４１、７１、
ファイルＣ：５３、９０、２６
ファイルＡ：１４、３０、５３、６０、８４、４１、７１、９０、２６
ファイルＢ：１４、３０、５３、６０、８４、２６
ファイルＣ：４１、７１、９０、
ファイルＡ：１４、３０、４１、５３、６０、７１、８４、２６、９０
ファイルＢ：１４、３０、４１、５３、６０、７１、８４
ファイルＣ：２６、９０
ファイルＡ：１４、２６、３０、４１、５３、６０、７１、８４、９０
ソート終了
以上からわかるように、連の個数が多いと、分割とマージの回数が多くなり、入出力回数が増大し、効率が悪くなります。
最も効率が悪いのは、ファイルＡが逆順にソートされているときです。