C++で2つの未ソート配列をマージしてソート済みの新しい配列を作成する方法

問題の概要

本記事では、2つのソートされていない（未ソート）配列を受け取り、それらを1つの新しい配列にマージしたうえで、昇順にソートされた結果を返す関数をC++で実装する方法を解説します。

具体的な入力と期待される出力は以下の通りです。

arr1[] = {10, 5, 7, 2}
arr2[] = {4, 17, 9, 3}
result[] = {2, 3, 4, 5, 7, 9, 10, 17}

アルゴリズム

実装のアプローチは非常にシンプルで、次の2ステップで構成されます。

1. 2つの未ソート配列を1つの新しい配列へマージ（連結）する。
2. 新しく作成した配列全体をソートする。

C++では、STL（標準テンプレートライブラリ）が提供する merge() 関数や sort() 関数を利用することで、簡潔かつ効率的にこの処理を実現できます。

サンプルコード

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

void mergeAndSort(int *arr1, int n1, int *arr2, int n2, int *result){
    merge(arr1, arr1 + n1, arr2, arr2 + n2, result);
    sort(result, result + n1 + n2);
}

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

int main(){
    int arr1[] = {10, 5, 7, 2};
    int arr2[] = {4, 17, 9, 3};
    int result[SIZE(arr1) + SIZE(arr2)];

    cout << "First array: " << endl;
    displayArray(arr1, SIZE(arr1));

    cout << "Second array: " << endl;
    displayArray(arr2, SIZE(arr2));

    mergeAndSort(arr1, SIZE(arr1), arr2, SIZE(arr2), result);

    cout << "Merged and sorted array: " << endl;
    displayArray(result, SIZE(arr1) + SIZE(arr2));

    return 0;
}

コードのポイント

• SIZE マクロ： 配列の要素数を sizeof(arr) / sizeof(arr[0]) で求める定番の手法です。
• merge() 関数： 2つの範囲の要素を1つの出力先へコピーします。なお、merge() は本来ソート済みの範囲を前提とするため、ここでは単純な連結として機能させた後に sort() で並べ替えています。
• sort() 関数： 結果配列の先頭から末尾までを昇順にソートします。

実行結果

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

First array:
10 5 7 2
Second array:
4 17 9 3
Merged and sorted array:
2 3 4 5 7 9 10 17

まとめ

2つの未ソート配列をソート済みの1つの配列に統合する処理は、「マージしてからソートする」というシンプルな手順で実装できます。計算量は要素数の合計を N とした場合、O(N log N) となります。より効率化したい場合は、各配列を個別に先にソートしておき、その後 merge() を使って線形時間 O(N) でマージする方法も検討するとよいでしょう。