マージ

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

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

1. 二つの線形リスト（${\displaystyle A}$、${\displaystyle B}$）と空（nil）の線形リスト ${\displaystyle L}$ を用意する。
2. ${\displaystyle A}$、${\displaystyle B}$ の先頭を調べ値の小さい方のリストの先頭を取り出し、その値を ${\displaystyle L}$ の最後尾に追加する。
3. ${\displaystyle A}$、${\displaystyle B}$ のどちらかが空になるまで上記の操作を繰り返す。
4. 最後に空になっていない方のリストの残りの要素を全て ${\displaystyle 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 も昇順に並んでいる。 この性質を利用してソートを行うアルゴリズムをマージソートという。