マージのソースを表示

{{otheruses}}
'''マージ''' (merge) は、「併合する」「合併する」という意味合いの英単語である。日本語では、[[計算機科学]]や[[情報工学]]の文脈でよく用いられる。これらの分野における「マージ」とは、複数の[[データベース]]や[[ファイル_(コンピュータ)|ファイル]]、[[プログラム_(コンピュータ)|プログラム]]などを一つにまとめる行為を意味する。

また、以下で述べるような、二つの[[線形リスト]]を一つにまとめる[[アルゴリズム]]のことをマージアルゴリズムという。

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

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

# 二つの線形リスト（<math>A</math>、<math>B</math>）と空（[[Null|nil]]）の線形リスト <math>L</math> を用意する。
# <math>A</math>、<math>B</math> の先頭を調べ値の小さい方のリストの先頭を取り出し、その値を <math>L</math> の最後尾に追加する。
# <math>A</math>、<math>B</math> のどちらかが空になるまで上記の操作を繰り返す。
# 最後に空になっていない方のリストの残りの要素を全て <math>L</math> の最後尾に追加する。

例として

 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 も昇順に並んでいる。
この性質を利用して[[ソート]]を行うアルゴリズムを[[マージソート]]という。

{{Computer-stub}}
{{デフォルトソート:まあし}}
[[Category:アルゴリズム]]