マージアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:26 UTC 版)
マージアルゴリズムとは二つの線形リストを一つにまとめるアルゴリズムのことである。主に関数型言語で使用される。 このアルゴリズムは以下のような動作で行う（この例では先頭の値が小さい方を優先することにする）。 二つの線形リスト（ A {\displaystyle A} 、 B {\displaystyle B} ）と空（nil）の線形リスト L {\displaystyle L} を用意する。 A {\displaystyle A} 、 B {\displaystyle B} の先頭を調べ値の小さい方のリストの先頭を取り出し、その値を L {\displaystyle L} の最後尾に追加する。 A {\displaystyle A} 、 B {\displaystyle B} のどちらかが空になるまで上記の操作を繰り返す。 最後に空になっていない方のリストの残りの要素を全て L {\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 も昇順に並んでいる。この性質を利用してソートを行うアルゴリズムをマージソートという。 この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。
※この「マージアルゴリズム」の解説は、「マージ」の解説の一部です。
「マージアルゴリズム」を含む「マージ」の記事については、「マージ」の概要を参照ください。
- マージアルゴリズムのページへのリンク
