マージアルゴリズムとは｜2つのソート済みリストを統合する仕組みを解説

マージアルゴリズムとは

マージ（併合）アルゴリズムは、2つの整列済み（ソート済み）リストを1つの整列済みリストに統合するための基本的なアルゴリズムです。さまざまな場面で利用されており、特にマージソートでは、分割された各部分リストを並べ替えた後、それらを大きなリストへと結合する段階でこのマージ処理が必須となります。

基本的な考え方

アプローチは非常にシンプルです。まず2つのリストを用意し、それぞれの先頭要素を指す2つのポインタを準備します。

次に、両ポインタが指す値を比較し、小さい方の要素を結果となる統合リストへ取り出します。そして、取り出した要素が属していた側のポインタを1つ進めます。この操作を、どちらか一方のリストが空になるまで繰り返します。最後に、まだ要素が残っている側のリストを、統合リストの末尾にそのまま連結すれば完成です。

下の図を見ると、一連の流れがより直感的につかめるでしょう。

具体例

たとえば、次の2つのソート済みリストを統合する場合を考えてみます。

• 左リスト：[10, 23, 51]
• 右リスト：[7, 15, 40]

先頭同士を比較すると 10 ＞ 7 なので 7 を取り出し、続いて 10 と 15 を比較して 10 を取り出す……という要領で進めます。右リストが先に空になった時点で、左リストに残った 51 を末尾に追加します。

結果：[7, 10, 15, 23, 40, 51]

アルゴリズム（擬似コード）

Merge(array, left, middle, right) −

Begin
    nLeft := middle − left + 1
    nRight := right − middle
    左側用の配列 leftArr（サイズ nLeft）と
    右側用の配列 rightArr（サイズ nRight）を定義する
    for i := 0 to nLeft−1 do
        leftArr[i] := array[left + i]
    done
    for j := 0 to nRight−1 do
        rightArr[j] := array[middle + j + 1]
    done
    i := 0, j := 0, k := left
    while i < nLeft AND j < nRight do
        if leftArr[i] <= rightArr[j] then
            array[k] := leftArr[i]
            i := i + 1
        else
            array[k] := rightArr[j]
            j := j + 1
        end if
        k := k + 1
    done
    while i < nLeft do
        array[k] := leftArr[i]
        i := i + 1
        k := k + 1
    done
    while j < nRight do
        array[k] := rightArr[j]
        j := j + 1
        k := k + 1
    done
End

この擬似コードでは、まず元の配列を中央（middle）で左右2つの部分配列にコピーし、それぞれをソート済みとして扱います。その後、両者の先頭から順に比較しながら元の配列へ書き戻していき、どちらかに余りが出ればそれをそのまま後ろへ詰める、という構造になっています。

計算量

マージ処理では、2つのリストの要素数をそれぞれ n、m としたとき、すべての要素をちょうど1回ずつ比較・格納するだけで完了します。

• 時間計算量：O(n + m)
• 空間計算量：O(n + m)（統合結果を格納する作業領域が必要）

線形時間で安定した結果が得られるため、マージソートの中核処理としてだけでなく、外部ソートや大量データの結合処理など、実務上のさまざまなシーンでも活用されています。