ソートとマージについて（４）マージ
４．マージ
マージとは統合という意味ですが、２つ以上のソート済みデータを１本化する作業を言います。
それぞれの集合のデータがソート済であることが前提です。（１件のみでもソート済です）
4.1 マージされていく様子
例えば、昇順でソート済データ A()とB()をD()に統合する場合
①A()のデータとB()のデータを先頭から順に比較
A()の方が小さければA()の値をD()へ保存し、A()の検索位置を次へ移動する。
逆に、B()の方が小さければB()の値をD()へ保存し、B()の検索位置を次へ移動する。
D()の挿入位置を次へ移動する。
②A()のデータのすべてをD()へ保存し終わった場合
B()のデータがまだ残っている場合は、 B()をD()に保存し、B()の検索位置を次へ移動する。
D()の挿入位置を次へ移動する。
③B()のデータのすべてをD()へ保存し終わった場合
A()のデータがまだ残っている場合は、A()をD()に保存し、A()の検索位置を次へ移動する。
D()の挿入位置を次へ移動する。
④A(),B()共にすべてのデータをD()に保存し終わったら終了、です。
サンプルデータが昇順にマージされていく様子です。
1回目：A(1)とB(1)を比較、A(1)をD(1)へ保存
2回目：A(1)は保存済なので、A(2)とB(1)を比較、B(1)をD(2)へ保存
3回目：A(1)B(1)は保存済なので、A(2)とB(2)を比較、A(2)をD(3)へ保存
・・・
8回目：B()は残っていないのでA(5)をD(8)へ保存
9回目：B()は残っていないのでA(6)をD(9)へ保存
4.2 フローチャート
フローチャートは下記のようになります。
次回はマージ＆ソートの予定です。
