【C++入門】STLのstd::merge()を使ってソート済み2つの配列を高速にマージする方法

本記事では、C++ STLのstd::merge()関数を使用して、ソート済みの2つの配列を素早くマージ（統合）する方法について解説します。

問題を解く前に、まずはC++ STLにおけるstd::merge()の基本から見ていきましょう。

std::merge()とは？

std::merge()は、C++標準ライブラリ（STL）の<algorithm>ヘッダーファイルで定義されている組み込み関数です。

merge()は、ソート済みの2つの範囲（レンジ）をマージするために使用され、2つのソート済み範囲を結合して、1つのソート済み範囲を生成します。すべての要素が小なり演算子（<）によって比較されるため、出力される3つ目の範囲も自動的にソートされた状態になります。

std::merge()で2つのソート済み配列を素早くマージするには？

ここでは、ソート済みの2つの配列 arr1[] と arr2[] が与えられ、C++ STLで利用可能な merge() 関数を使って、これらを別の空の配列（例：arr3[]）にマージして格納することを目標とします。

手順

• まず、両方の配列のサイズを計算します（arr[size_arr]、brr[size_brr]）。次に、両方のサイズの合計を要素数とする3つ目の配列 final[size_arr + size_brr] を定義します。

• 続いて、merge(arr, (arr + size_arr), brr, (brr + size_brr), final); のように merge() 関数を呼び出し、2つの配列を3つ目の配列へマージします。

サンプルコード

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int arr[] = {1, 2, 3};
    int size_arr = sizeof(arr)/sizeof(arr[0]);
    int brr[] = {4, 5, 6};
    int size_brr = sizeof(brr)/sizeof(brr[0]);
    int final[size_arr + size_brr];
    merge(arr, (arr + size_arr), brr, (brr + size_brr), final);
    cout<<"マージ後の最終配列: ";
    for (int i = 0; i < (size_brr + size_arr); i++)
        cout << final[i] << " ";
    return 0;
}

実行結果

マージ後の最終配列: 1 2 3 4 5 6

このように、std::merge()を活用すれば、ソート済みの2つの配列をわずか数行のコードで効率的に統合できます。マージ処理の計算量はO(n+m)（nとmはそれぞれの配列の要素数）であり、非常に高速です。