C++で2つのソート済み配列をマージする方法|効率的なアルゴリズムと実装例

問題の概要

ソート済みの2つの配列が与えられたとき、それらを1つのソート済み配列へマージ(統合)する関数を作成します。これはマージソートの中核となる処理であり、技術面接や競技プログラミングでも頻出のテーマです。

Arr1[] = {10, 15, 17, 20}
Arr2[] = {5, 9, 13, 19}
Result[] = {5, 9, 10, 13, 15, 17, 19, 20}

アプローチのポイント

単純に2つの配列を連結してから再ソートすることも可能ですが、それぞれがすでにソート済みであるという性質を活かせば、ツーポインタ(2つのインデックス)手法によって O(n1 + n2) の計算量で効率的にマージできます。

アルゴリズム

1. 両方の配列を先頭から走査する
   1.1. arr1[i] < arr2[j] の場合
      1.1.1. arr1[i] を結果配列に追加する
      1.1.2. インデックス i と結果配列のインデックス k を1つ進める
   1.2. それ以外の場合(arr2[j] <= arr1[i])
      1.2.1. arr2[j] を結果配列に追加する
      1.2.2. インデックス j と結果配列のインデックス k を1つ進める
2. どちらか一方の配列が尽きるまで手順を繰り返す
3. 残った側の配列の要素をすべて結果配列の末尾にコピーする
4. 結果の配列を返す

C++での実装例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

void mergeSortedArrays(int *arr1, int n1, int *arr2, int n2, int *result){
    int i = 0, j = 0, k = 0;
    // 両方の配列に要素が残っている間、小さい方を結果配列へ移す
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            result[k] = arr1[i];
            ++k;
            ++i;
        } else {
            result[k] = arr2[j];
            ++k;
            ++j;
        }
    }
    // arr1 に残った要素をコピー
    while (i < n1) {
        result[k] = arr1[i];
        ++k;
        ++i;
    }
    // arr2 に残った要素をコピー
    while (j < n2) {
        result[k] = arr2[j];
        ++k;
        ++j;
    }
}

void displayArray(int *arr, int n){
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main(){
    int arr1[] = {10, 15, 17, 20};
    int arr2[] = {5, 9, 13, 19};
    int result[SIZE(arr1) + SIZE(arr2)];
    cout << "First sorted array:" << endl;
    displayArray(arr1, SIZE(arr1));
    cout << "Second sorted array:" << endl;
    displayArray(arr2, SIZE(arr2));
    mergeSortedArrays(arr1, SIZE(arr1), arr2, SIZE(arr2), result);
    cout << "Final sorted array:" << endl;
    displayArray(result, SIZE(result));
    return 0;
}

関数 mergeSortedArrays は2つのソート済み配列を受け取り、マージ結果を result 配列に書き込みます。補助関数 displayArray は配列の内容を標準出力に表示するためのものです。

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

First sorted array:
10 15 17 20
Second sorted array:
5 9 13 19
Final sorted array:
5 9 10 13 15 17 19 20

計算量

• 時間計算量: O(n1 + n2) — 各配列の要素をそれぞれ一度だけ走査します。
• 空間計算量: O(n1 + n2) — マージ結果を格納するための補助配列が必要です。

まとめ

ソート済み配列のマージは、各配列の先頭要素を比較しながら小さい方を順に取り出していくシンプルな手法で実現できます。この考え方はマージソートだけでなく、外部ソートや連結リストの統合など、さまざまな場面で応用される重要なテクニックです。