JavaScriptでソート済み配列をマージする方法を解説

ソート済み配列のマージとは

JavaScriptでは、昇順にソートされた2つの配列を1つに統合し、その結果もソートされた状態に保ちたい場面があります。例えば、次のような2つの配列を考えてみましょう。

const arr1 = [1, 2, 3, 0, 0, 0];
const arr2 = [2, 5, 6];

ここで求められるのは、これら2つの配列を受け取り、全要素を昇順に並べ替えた新しい配列を返すJavaScript関数です。上記の配列の場合、期待される出力は以下のようになります。

const output = [1, 2, 2, 3, 5, 6];

注意したいのは、arr1の末尾にある「0」がマージ用に確保されたプレースホルダーであるという点です。単純に連結してソートすると、この0まで出力に含まれてしまうため、少し工夫が必要になります。

解決策1： スプレッド構文とsort()を使うシンプルな方法

プレースホルダーが不要なケースでは、2つの配列を連結してからsort()メソッドで並べ替えるのが最も手軽です。

const arr1 = [1, 2, 3];
const arr2 = [2, 5, 6];

const mergeSortedArrays = (arr1, arr2) => {
  return [...arr1, ...arr2].sort((a, b) => a - b);
};

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

出力結果

[1, 2, 2, 3, 5, 6]

sort()はデフォルトで要素を文字列として比較するため、数値配列の場合は必ず比較関数(a, b) => a - bを指定してください。これを省略すると、意図しない並び順になってしまうことがあります。

解決策2： 余白（0）を含む配列を正しく処理する

arr1の末尾に0の余白がある場合（LeetCodeの「Merge Sorted Array」問題など）は、有効な要素数をもとに余白を除外してからマージします。

const arr1 = [1, 2, 3, 0, 0, 0]; // 有効な要素は3個
const arr2 = [2, 5, 6];

const mergeSortedArrays = (arr1, arr2, m, n) => {
  // arr1から有効なm個、arr2からn個の要素を取り出して結合
  const merged = [...arr1.slice(0, m), ...arr2.slice(0, n)];
  merged.sort((a, b) => a - b);

  // 結果をarr1へ書き戻す
  for (let i = 0; i < merged.length; i++) {
    arr1[i] = merged[i];
  }
  return arr1;
};

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

出力結果

[1, 2, 2, 3, 5, 6]

より効率的な方法： 2ポインタによるマージ

両方の配列がすでにソート済みであれば、2つのポインタで先頭から小さい方を順に選んでいく手法が使えます。計算量はO(m + n)となり、sort()を使うO((m + n) log(m + n))よりも高速に動作します。

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

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      result.push(arr1[i++]);
    } else {
      result.push(arr2[j++]);
    }
  }

  // 片方に残った要素をすべて追加
  while (i < arr1.length) result.push(arr1[i++]);
  while (j < arr2.length) result.push(arr2[j++]);

  return result;
};

console.log(mergeTwoSortedArrays([1, 2, 3], [2, 5, 6]));

出力結果

[1, 2, 2, 3, 5, 6]

まとめ

ソート済み配列のマージには、「スプレッド構文＋sort()」による手軽な方法と、大規模データに強い「2ポインタ方式」があります。コードの簡潔さを優先するなら前者、パフォーマンスを優先するなら後者を選ぶとよいでしょう。いずれの場合も、数値を扱う際のsort()の比較関数指定だけは忘れないようにしてください。