JavaScript | 「再帰の動き」を図解で追う

では「マージソート」を図解で追ってみましょう。クイックソートと並んで有名な「分割統治法」のアルゴリズムです。

マージソートの考え方

1. 配列を半分に分割する
2. 左右それぞれを再帰的にソートする
3. 左右のソート済み配列を「マージ（結合）」して完成

コード例

function mergeSort(arr) {
  if (arr.length <= 1) return arr; // 終了条件

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([3, 7, 2, 5, 1]));
// [1, 2, 3, 5, 7]

function mergeSort(arr) {
  if (arr.length <= 1) return arr; // 終了条件

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([3, 7, 2, 5, 1]));
// [1, 2, 3, 5, 7]

実行の流れ（例: [3, 7, 2, 5, 1]）

1. [3,7,2,5,1] を半分に分ける → [3,7] と [2,5,1]
2. [3,7] → [3] と [7] に分ける → マージして [3,7]
3. [2,5,1] → [2] と [5,1] に分ける
   • [5,1] → [5] と [1] → マージして [1,5]
   • [2] と [1,5] をマージ → [1,2,5]
4. [3,7] と [1,2,5] をマージ → [1,2,3,5,7]

図でイメージ

[3,7,2,5,1]
   ↓ 分割
[3,7]       [2,5,1]
 ↓           ↓
[3] [7]     [2] [5,1]
             ↓
           [5] [1]

マージしていくと…

[3,7]   [1,5]
   ↓       ↓
   [3,7]   [1,2,5]

最後にマージ
[1,2,3,5,7]

クイックソートとの違い

• クイックソート: ピボットを基準に「小さい」「大きい」に分ける
• マージソート: 半分に分けて「マージ」で整列させる
• 共通点: どちらも「分割統治法」で再帰を使う

👉 これで「探索（迷路）」「クイックソート」「マージソート」と、再帰の応用を一通り見ました。