JavaScriptで2つのソート済み配列を1つのソート済み配列にマージする方法

問題

2つの数値のソート済み配列を受け取り、両方の配列のすべての要素を新しい配列へマージし、同じ順序でソートされた状態の新しい配列として返すJavaScript関数を作成する必要があります。

この操作はマージソートの中核となる処理でもあり、効率的なアルゴリズム設計における重要なテクニックです。concat()後にsort()する方法もありますが、すでにソート済みの配列同士をマージする場合は、両端ポインタ（Two Pointers）を使ったアプローチの方がはるかに効率的です。

解決のアプローチ：Two Pointers（双方向ポインタ）

基本的な考え方は以下の通りです。

• インデックス変数 i と j を用意し、それぞれ arr1 と arr2 の先頭を指します。
• 両方の配列に未処理の要素が残っている間、値が小さい方を結果配列に追加し、対応するインデックスを1つ進めます。
• どちらか一方の配列が尽きたら、残ったもう一方の配列の要素をすべて結果に追加します。

コード例

const arr1 = [1, 3, 4, 5, 6, 8];
const arr2 = [4, 6, 8, 9, 11];

const mergeSortedArrays = (arr1 = [], arr2 = []) => {
    const res = [];
    let i = 0;
    let j = 0;

    // 両方の配列に要素が残っている間、小さい方を選んで追加
    while(i < arr1.length && j < arr2.length){
        if(arr1[i] < arr2[j]){
            res.push(arr1[i]);
            i++;
        }else{
            res.push(arr2[j]);
            j++;
        }
    };

    // arr1 に残った要素をすべて追加
    while(i < arr1.length){
        res.push(arr1[i]);
        i++;
    };

    // arr2 に残った要素をすべて追加
    while(j < arr2.length){
        res.push(arr2[j]);
        j++;
    };

    return res;
};

console.log(mergeSortedArrays(arr1, arr2));

出力結果

[ 1, 3, 4, 4, 5, 6, 6, 8, 8, 9, 11 ]

処理のポイントと計算量

• 時間計算量：O(m + n) — m と n はそれぞれの配列の長さです。各要素は一度だけ比較・追加されるため、非常に効率的です。
• 空間計算量：O(m + n) — マージ結果を格納するための新しい配列が必要になります。
• 元の配列を保持： 入力配列 arr1 と arr2 は変更されず、常に新しい配列が返されます。

なお、[...arr1, ...arr2].sort((a, b) => a - b) のようにスプレッド構文と sort() を組み合わせれば1行でも書けますが、その場合の時間計算量は O((m+n) log(m+n)) となります。大規模なデータや頻繁なマージ処理では、本記事のTwo Pointers方式の方がパフォーマンス面で有利です。