マージマージ (merge) は、「併合する」「合併する」という意味合いの英単語である。日本語では、計算機科学や情報工学の文脈でよく用いられる。これらの分野における「マージ」とは、複数のデータベースやファイル、プログラムなどを一つにまとめる行為を意味する。 また、以下で述べるような、二つの線形リストを一つにまとめるアルゴリズムのことをマージアルゴリズムという。 マージアルゴリズムマージアルゴリズムとは二つの線形リストを一つにまとめるアルゴリズムのことである。主に関数型言語で使用される。 このアルゴリズムは以下のような動作で行う(この例では先頭の値が小さい方を優先することにする)。
例として 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 も昇順に並んでいる。 この性質を利用してソートを行うアルゴリズムをマージソートという。 |