マージソートとは？分割統治法の仕組みとC++実装例を解説

マージソート（Merge Sort）は、分割統治法（Divide and Conquer）に基づいた代表的なソートアルゴリズムです。データセット全体を小さな部分に分割し、それぞれをソートしながら大きな塊へと統合していくことで、最終的に整列済みの配列を作り上げます。

マージソートの大きな特徴は、最悪ケースでも計算量が O(n log n) と安定している点です。クイックソートのように最悪時に O(n²) へ劣化することがないため、性能の予測がしやすく、大規模なデータや外部ソートにも広く利用されています。

マージソートの計算量

• 時間計算量： 最良・平均・最悪のすべてのケースで O(n log n)
• 空間計算量： O(n)（マージ用の一時配列が必要）

入力と出力の例

Input:
整列されていないリスト: 14 20 78 98 20 45
Output:
ソート前の配列: 14 20 78 98 20 45
ソート後の配列: 14 20 20 45 78 98

アルゴリズムの手順

マージソートは「マージ（統合）」と「再帰的な分割」の2つの処理で構成されます。まず、統合処理を担う merge(array, left, middle, right) の擬似コードを示します。

merge(array, left, middle, right)

入力： データ配列、左端・中央・右端のインデックス

出力： 統合されたリスト

Begin
    nLeft := m - left + 1
    nRight := right - m
    左右それぞれのサイズ nLeft、nRight の配列 leftArr と rightArr を定義

    for i := 0 to nLeft do
        leftArr[i] := array[left + i]
    done

    for j := 0 to nRight 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
        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

次に、配列を再帰的に分割していく mergeSort(array, left, right) の擬似コードです。

mergeSort(array, left, right)

入力： データ配列、およびその下限・上限インデックス

出力： ソート済みの配列

Begin
    if lower < right then
        mid := left + (right - left) / 2
        mergeSort(array, left, mid)
        mergeSort(array, mid + 1, right)
        merge(array, left, mid, right)
End

C++による実装例

以下は、マージソートをC++で実装したサンプルプログラムです。ユーザーから要素数と値を入力すると、ソート前後の配列を表示します。

#include<iostream>
using namespace std;

void swapping(int &a, int &b) { // aとbの中身を入れ替える
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void merge(int *array, int l, int m, int r) {
    int i, j, k, nl, nr;
    // 左右サブ配列のサイズ
    nl = m-l+1; nr = r-m;
    int larr[nl], rarr[nr];

    // 左右のサブ配列に要素をコピー
    for(i = 0; i<nl; i++)
        larr[i] = array[l+i];
    for(j = 0; j<nr; j++)
        rarr[j] = array[m+1+j];

    i = 0; j = 0; k = l;
    // 一時配列を元の配列へマージ

    while(i < nl && j<nr) {
        if(larr[i] <= rarr[j]) {
            array[k] = larr[i];
            i++;
        }else{
            array[k] = rarr[j];
            j++;
        }
        k++;
    }

    while(i<nl) {      // 左配列に残った要素を処理
        array[k] = larr[i];
        i++; k++;
    }

    while(j<nr) {      // 右配列に残った要素を処理
        array[k] = rarr[j];
        j++; k++;
    }
}

void mergeSort(int *array, int l, int r) {
    int m;
    if(l < r) {
        int m = l+(r-l)/2;
        // 前半と後半をそれぞれソート
        mergeSort(array, l, m);
        mergeSort(array, m+1, r);
        merge(array, l, m, r);
    }
}

int main() {
    int n;
    cout << "要素数を入力してください: ";
    cin >> n;
    int arr[n]; // 指定された要素数の配列を作成
    cout << "要素を入力してください:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "ソート前の配列: ";
    display(arr, n);
    mergeSort(arr, 0, n-1); // 最後のインデックスは (n-1)
    cout << "ソート後の配列: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 6
Enter elements:
14 20 78 98 20 45
Array before Sorting: 14 20 78 98 20 45
Array after Sorting: 14 20 20 45 78 98

まとめ

マージソートは、配列を半分ずつに分割し、ソート済みの部分同士を順に統合することで整列を実現するアルゴリズムです。常に O(n log n) の時間計算量を保証する一方で、O(n) の追加メモリが必要というトレードオフがあります。安定ソートである点も特徴の一つで、同じ値を持つ要素の相対的な順序が保持されるため、実務でも信頼性の高い選択肢となります。