マージ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

マージとは「併合する」、「合併する」という意味であり、情報工学の用語としてよく用いられる。

広義には複数のデータベースやファイル、プログラムなどを一つにまとめる行為を意味する。

狭義には以下で述べる二つの線形リストを一つにまとめるアルゴリズムのことである。

[編集] マージアルゴリズム

マージアルゴリズムとは二つの線形リストを一つにまとめるアルゴリズムのことである。主に関数型言語で使用される。

このアルゴリズムは以下のような動作で行う（この例では先頭の値が小さい方を優先することにする）。

1. 二つの線形リスト（A,B とおく）と空（nil）の線形リスト L を用意する。
2. A,B の先頭を調べ値の小さい方のリストの先頭を取り出し、その値をL　の最後尾に追加する。
3. A,B　のどちらかが空になるまで上記の操作を繰り返す。
4. 最後に空になっていない方のリストの残りの要素を全て L の最後尾に追加する。

例として

A = (2 5 7 9)
B = (1 3 4 6 8)

というリストをマージする、先頭を比較すると

A = (2 5 7 9)
B = (1 3 4 6 8) → (3 4 6 8)
L = (1)

A = (2 5 7 9) → (5 7 9)
B = (3 4 6 8)
L = (1 2)

A = (5 7 9)
B = (3 4 6 8) → (4 6 8)
L = (1 2 3)

A = (5 7 9)
B = (4 6 8) → (6 8)
L = (1 2 3 4)

以下 A,B が空になるまで繰り返すと

L = (1 2 3 4 5 6 7 8 9)

というリストができあがる。この操作にかかる時間は A,B のリスト長の長い方に比例する。 例から解るように、A と B が昇順にならんでいる場合、一つにまとめたリスト L も昇順に並んでいる。 この性質を利用してソートを行うアルゴリズムをマージソートという。