マージアルゴリズム

マージとは

「併合」という意味で、複数の配列や連結リストなどのデータ列を1つにまとめることをいう。

単純に複数の配列を併合するならば、それぞれの配列の長さを合計した長さ以上の配列を用意し、すべてをそこに格納してしまえばよい（順序など関係なく）。ここでは、複数の整列済み配列をマージし、1つの整列済み配列をつくることを考える。

アルゴリズム

1. マージする配列をA, Bとする（A,Bはそれぞれ整列済み。マージ後の結果を格納する配列Lを用意する。2 へ。
2. A, Bの先頭の要素を見て、小さい方の要素をリストから取り出し、Lに追加する。 　A, Bどちらかの配列が空になるまで、2 を繰り返す。
3. 空になっていない方のリストを、先頭から順にすべてLに追加する。

最初の段階。ここからスタート。 完了。