C++による3方向マージソートの実装と解説

マージソートは、配列を再帰的に2つの部分に分割し、それぞれをソートしてからマージ（併合）するアルゴリズムです。このバリエーションの一つに「3方向マージソート（3-way Merge Sort）」があり、配列を2つではなく3つの部分に分割して処理を行います。

基本概念

通常のマージソートでは、配列を半分のサイズの部分配列に再帰的に分解します。一方、3方向マージソートでは、配列を3分の1のサイズの部分配列に分解していきます。分割数が増えることで再帰の深さが浅くなる（底が3の対数になる）という特徴があります。

実行例

入力: 46, -1, -44, 79, 31, -41, 11, 20, 74, 94
出力: -44 -41 -1 11 20 31 46 74 79 94

入力: 24, -18
出力: -18 24

時間計算量

3方向マージソートの時間計算量は O(n log₃ n) です。通常のマージソート（O(n log₂ n)）と比較すると、定数倍の違いはありますが、漸近的な計算量クラスは同じ O(n log n) です。分割数を増やすことで再帰呼び出しのオーバーヘッドを減らせる可能性がありますが、マージ処理における比較回数が増えるトレードオフがあります。

C++ 実装例

以下は、3方向マージソートの完全な実装コードです。元の配列と作業用配列を入れ替えながら再帰的にソートを行い、最後に結果を元の配列にコピーバックします。

// C++ Program for performing 3 way Merge Sort
#include <bits/stdc++.h>
using namespace std;

// 3つのソート済み部分配列をマージする関数
// gArray: ソース配列, destArray: 宛先配列
// 範囲: [low, mid1), [mid1, mid2), [mid2, high)
void merge3Way(int gArray[], int low, int mid1, int mid2, int high, int destArray[]) {
    int i = low, j = mid1, k = mid2, l = low;

    // 3つの範囲すべてに要素が残っている間、最小値を選択
    while ((i < mid1) && (j < mid2) && (k < high)) {
        if (gArray[i] < gArray[j]) {
            if (gArray[i] < gArray[k]) {
                destArray[l++] = gArray[i++];
            } else {
                destArray[l++] = gArray[k++];
            }
        } else {
            if (gArray[j] < gArray[k]) {
                destArray[l++] = gArray[j++];
            } else {
                destArray[l++] = gArray[k++];
            }
        }
    }

    // 残りの2範囲、または1範囲のマージ処理
    while ((i < mid1) && (j < mid2)) {
        destArray[l++] = (gArray[i] < gArray[j]) ? gArray[i++] : gArray[j++];
    }
    while ((j < mid2) && (k < high)) {
        destArray[l++] = (gArray[j] < gArray[k]) ? gArray[j++] : gArray[k++];
    }
    while ((i < mid1) && (k < high)) {
        destArray[l++] = (gArray[i] < gArray[k]) ? gArray[i++] : gArray[k++];
    }

    // 残りの1範囲をコピー
    while (i < mid1) destArray[l++] = gArray[i++];
    while (j < mid2) destArray[l++] = gArray[j++];
    while (k < high) destArray[l++] = gArray[k++];
}

// 再帰的なソート関数
void mergeSort3WayRec(int gArray[], int low, int high, int destArray[]) {
    // 要素数が1以下なら終了
    if (high - low < 2) return;

    // 3等分する境界を計算
    int mid1 = low + ((high - low) / 3);
    int mid2 = low + 2 * ((high - low) / 3) + 1;

    // ソースと宛先を入れ替えて再帰呼び出し（インプレース風に見せるため）
    mergeSort3WayRec(destArray, low, mid1, gArray);
    mergeSort3WayRec(destArray, mid1, mid2, gArray);
    mergeSort3WayRec(destArray, mid2, high, gArray);

    // マージして元の配列(gArray)に結果を書き戻す
    merge3Way(destArray, low, mid1, mid2, high, gArray);
}

// エントリーポイント関数
void mergeSort3Way(int gArray[], int n) {
    if (n == 0) return;

    // 作業用配列を確保し、初期データをコピー
    vector<int> fArray(gArray, gArray + n);
    
    // ソート実行（fArrayをソース、gArrayを宛先として開始）
    mergeSort3WayRec(fArray.data(), 0, n, gArray);
    
    // 最終結果がgArrayに入っているため、コピーバックは不要だが
    // 再帰の深さが奇数の場合を考慮し、明示的にコピーするのが安全
    // （上記実装では深さに関わらずgArrayに結果が返る設計）
    // ここでは明示的にコピーしておく
    copy(fArray.begin(), fArray.end(), gArray);
}

// ドライバーコード
int main() {
    int data[] = {46, -1, -44, 79, 31, -41, 11, 20, 74, 94};
    int n = sizeof(data) / sizeof(data[0]);
    
    mergeSort3Way(data, n);
    
    cout << "After 3 way merge sort: ";
    for (int i = 0; i < n; i++) {
        cout << data[i] << " ";
    }
    cout << endl;
    return 0;
}

実行結果

After 3 way merge sort: -44 -41 -1 11 20 31 46 74 79 94

実装のポイント

• ダブルバッファリング: 再帰呼び出しのたびにソース配列と宛先配列を入れ替えることで、マージごとのデータコピーを避けています。
• 境界計算: mid1 = low + (high - low) / 3, mid2 = low + 2 * (high - low) / 3 + 1 として、要素数が3で割り切れない場合も考慮しています。
• マージロジック: 3方向の比較はネストしたif文で行い、いずれかの部分配列が空になった時点で2方向、1方向のマージに移行します。

まとめ

3方向マージソートは、分割数を増やすことで再帰の深さを log3 n に抑えるアプローチです。理論上の比較回数は増えますが、キャッシュ効率や関数呼び出しオーバーヘッドの観点から、特定の環境やデータサイズでは通常の2方向マージソートより高速になるケースがあります。C++ で実装する際は、std::vector などの動的配列を用いてメモリ管理を安全に行うのが推奨されます。