C++でマージソートを実装する方法を解説

マージソート（Merge Sort）は、分割統治法（divide and conquer）に基づいたソートアルゴリズムです。データセット全体をより小さな部分に分割し、それらをソートされた順序で統合（マージ）していくことで、最終的に整列済みのリストを作り上げます。最悪の場合でも計算量が低く抑えられるため、どのような入力データに対しても安定したパフォーマンスを発揮できるのが大きな特徴です。

マージソートの計算量

• 時間計算量： すべてのケースで O(n log n)

• 空間計算量： O(n)

クイックソートなどは最悪ケースで O(n²) まで劣化しますが、マージソートはデータの初期状態に依存せず常に O(n log n) を保証する点で優れています。

入力 − 未ソートのリスト：14 20 78 98 20 45
出力 − ソート後の配列：14 20 20 45 78 98

アルゴリズム

merge(array, left, middle, right)

入力： データ配列、left（左端）、middle（中央）、right（右端）のインデックス

出力： 統合（マージ）されたリスト

Begin
    nLeft := m - left + 1
    nRight := right - m
    左右の部分配列 leftArr と rightArr をそれぞれ nLeft、nRight のサイズで定義する
    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)

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

出力： ソート済みの配列

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 << "Enter the number of elements: ";
    cin >> n;
    int arr[n];     // 指定された要素数で配列を作成
    cout << "Enter elements:" << endl;
    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    mergeSort(arr, 0, n-1);     // 最後のインデックスは (n-1)
    cout << "Array after Sorting: ";
    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) の追加メモリが必要となる点は、メモリ制約が厳しい環境では考慮が必要です。連結リストのソートや外部ソートなどにも応用できるため、ぜひ実装を通じて理解を深めてみてください。