JavaScriptで2つのソート済み配列をマージして、結果のソート済み配列を作成する方法

はじめに

本記事では、2つのソート済み（昇順に並べ替えられた）数値配列を受け取り、それらをマージして1つのソート済み配列として返すJavaScript関数の実装方法を解説します。

問題の概要

例えば、次の2つの配列が与えられたケースを考えてみましょう。

const arr1 = [2, 6, 6, 8, 9];
const arr2 = [1, 4, 5, 7];

この場合、期待される出力は以下の通りです。

const output = [1, 2, 4, 6, 6, 7, 8, 9];

実装のポイント

ここで紹介する手法では、新しい配列を用意する代わりに、arr1 の末尾から大きい値を詰めていくアプローチを採用しています。両方の配列がすでにソートされているため、それぞれの末尾要素を比較しながら、大きい方を結果の末尾へ配置していくことで、追加のメモリをほとんど使わずにマージできます。

サンプルコード

const arr1 = [2, 6, 6, 8, 9];
const arr2 = [1, 4, 5, 7];
const mergeSortedArrays = (arr1 = [], arr2 = []) => {
    let m = arr1.length;
    let n = arr2.length;
    let currentIndex = m + n;
    const checkNum1HasLargerNumber = (a, b) => {
        if (a < 0) {
            return false;
        };
        if (b < 0) {
            return true;
        };
        return arr1[a] >= arr2[b];
    };
    m -= 1;
    n -= 1;
    while (currentIndex--) {
        let hasNums1LargerNumber = checkNum1HasLargerNumber(m, n);
        arr1[currentIndex] = hasNums1LargerNumber ? arr1[m] : arr2[n];
        if (hasNums1LargerNumber) {
            m -= 1;
        } else {
            n -= 1;
        }
    };
};
mergeSortedArrays(arr1, arr2);
console.log(arr1);

コードの解説

• m と n は、それぞれ arr1・arr2 における現在の比較対象インデックスを表します。
• currentIndex は、結果となる配列の末尾から順に値を書き込んでいく位置です。
• 補助関数 checkNum1HasLargerNumber は、arr1 の末尾要素が arr2 の末尾要素以上かどうかを判定します。片方の配列の処理が完了（インデックスが負）した場合は、もう一方の配列の残りをそのままコピーします。
• このアルゴリズムの計算量は O(m + n) で、余分な配列を作らないため非常に効率的です。

実行結果

コンソールには以下のように出力されます。

[
    1, 2, 4, 5, 6,
    6, 7, 8, 9
]