1. はじめに

本記事は、私が学生時代にアルゴリズムを学ぶ上で苦手に感じてしまった原因である「マージソート」についてです！

【本記事でわかること】

再帰の仕組み🤝
マージソートで配列を並び替える方法🧑‍🤝‍🧑

【前回の記事】✨ JSでソートを知る ✨

基本のソートアルゴリズムである「選択ソート」「バブルソート」「クイックソート」についての内容と、JSのsort()メソッドについてまとめてあります！

1. はじめに
- マージソート
- 分割統治法
2. 再帰を理解する
- 再帰関数
  - 構成
- 再帰関数の使用
3. マージソート
- 仕組み
- JavaScriptでの実装
4. 最後に
- まとめ
- 参考

マージソート

マージソートは、配列を部分配列に分割し、並べ替えてからそれらを結合（merge）することで、ソートした配列を得ます。

図1. マージソートを使用した配列のソート

分割統治法

マージソートは、分割統治法に基づくアルゴリズムです。

分割統治法とは、大きな問題を小さな部分問題に分割し、それらの解決策を組み合わせることで全体の問題を解決する問題解決方法です。

図2. 分割統治法を使用した問題解決例

2. 再帰を理解する

マージソートに取り掛かる前に、まず「再帰」について知っておきたいです！

再帰関数

再帰とは、関数定義において自身の関数内で自分自身を呼び出すことです。

このような関数を、再帰関数と言います。

再帰関数を使用すると、コードが短くなり、可読性を高める効果があります。

図3. 再帰関数の呼び出しと実行手順イメージ

構成

再帰関数は、次の2つで構成されます。

再帰を停止する条件
- 無限に再帰関数が呼び出されないように、関数を修了する条件を設定する必要があります。
再帰呼び出し
- 問題をより小さな部分問題に分割し、それを引数に自分自身を呼び出します。呼び出すごとに、基底条件に近づく必要があります。

再帰関数の使用

再帰関数を実際に使用することで、処理の流れを理解したいです！💥

目的と制約に沿って、2つの方法でコードを書いてみます💥💥

【目的】からnまでの数値の合計を計算する関数の実装

【制約】nは正の整数

1. 反復を使用した実装

ループを使用して、1からnまで足し合わせていくシンプルでな方法です。 nから1まで減らしながら足し合わせるなど他にも方法がありそうです！

const sumFunc = (n) => {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
};

console.log(sumFunc(5)); // 15

2. 再帰関数を使用した実装

再帰関数を使用して、引数を減らしていきながら、自分自身を呼び出していく方法です。かっこいい！

const recursiveFunc = (n) => {
  if (n === 0) return 0;
  return n + recursiveFunc(n - 1);
};

console.log(recursiveFunc(5)); // 15

処理の流れ

コンソールに出力して処理の流れを見るため、以下のようにログを出しました。

const recursiveFunc = (n) => {
  if (n === 0) {
    console.log(`recursiveFunc(${n}) = 0`);
    return 0;
  }
  console.log(`recursiveFunc(${n}) = ${n} + recursiveFunc(${n - 1})`);
  return n + recursiveFunc(n - 1);
};

console.log(recursiveFunc(5)); // 15

出力結果

recursiveFunc(5) = 5 + recursiveFunc(4)
recursiveFunc(4) = 4 + recursiveFunc(3)
recursiveFunc(3) = 3 + recursiveFunc(2)
recursiveFunc(2) = 2 + recursiveFunc(1)
recursiveFunc(1) = 1 + recursiveFunc(0)
recursiveFunc(0) = 0
15

recursiveFunc(0) が呼び出されると、基底条件に当てはまり、0が返されます。そこからrecursiveFunc(1), recursiveFunc(2) …と出力結果の上方向に遡って数値を当てはめていくイメージです。

おまけ

シグマの公式を使用して計算することもできます！

const sumGaussFunc = (n) => {
  return (n * (n + 1)) / 2;
};

console.log(sumGaussFunc(5)); // 15

[参考] https://hiraocafe.com/note/sigmaformula.html

3. マージソート

仕組み

ソートの流れ

配列を半分に分割する
配列の要素が一つになるまで配列の分割を続ける
分割した配列の先頭の要素を比較して、値が小さい順に並ぶように配列を結合する
すべての部分配列が結合されるまで繰り返す

図1. マージソートを使用した配列のソート

メリット

O(n*log(n)) 時間で効率的な配列のソートが可能
同一の値がある場合、その順序が維持される

デメリット

データセットが小さい場合、他のソートアルゴリズムより時間で劣る
配列がソートされている場合でも、マージソートのプロセスを実行する

JavaScriptでの実装

再帰呼び出しがわかりやすいように、ログに出るようにしてあります。ご参考までに🐥

マージソートの実装

const merge = (leftArr, rightArr) => {
  console.log(`マージ: merge([${leftArr}], [${rightArr}])`);
  const result = [];
  const leftLen = leftArr.length;
  const rightLen = rightArr.length;
  let i = 0;
  let j = 0;

  while (i < leftLen && j < rightLen) {
    if (leftArr[i] < rightArr[j]) {
      result.push(leftArr[i]);
      i++;
    } else {
      result.push(rightArr[j]);
      j++;
    }
  }
  while (i < leftLen) {
    result.push(leftArr[i]);
    i++;
  }
  while (j < rightLen) {
    result.push(rightArr[j]);
    j++;
  }
  console.log('ソート結果:', result);
  console.log('------------------------------------------')
  return result;
};

const mergeSort = (inputArr) => {
  if (inputArr.length <= 1) {
    console.log(`分割終了: mergeSort([${inputArr}])`)
    return inputArr;
  };
  console.log(`mergeSort([${inputArr}])`);
  const mid = Math.floor(inputArr.length / 2);
  const leftArr = inputArr.slice(0, mid);
  const rightArr = inputArr.slice(mid);
  console.log(`分割: merge(mergeSort([${leftArr}]), mergeSort([${rightArr}]))`)
  return merge(mergeSort(leftArr), mergeSort(rightArr));
};

const unsortedArr = [7, 1, 9, 2, 6];
const sortedArr = mergeSort(unsortedArr);
console.log('ソート前:', unsortedArr);
console.log('ソート後:', sortedArr);

出力結果

mergeSort([7,1,9,2,6])
分割: merge(mergeSort([7,1]), mergeSort([9,2,6]))
mergeSort([7,1])
分割: merge(mergeSort([7]), mergeSort([1]))
分割終了: mergeSort([7])
分割終了: mergeSort([1])
マージ: merge([7], [1])
ソート結果: [ 1, 7 ]
------------------------------------------
mergeSort([9,2,6])
分割: merge(mergeSort([9]), mergeSort([2,6]))
分割終了: mergeSort([9])
mergeSort([2,6])
分割: merge(mergeSort([2]), mergeSort([6]))
分割終了: mergeSort([2])
分割終了: mergeSort([6])
マージ: merge([2], [6])
ソート結果: [ 2, 6 ]
------------------------------------------
マージ: merge([9], [2,6])
ソート結果: [ 2, 6, 9 ]
------------------------------------------
マージ: merge([1,7], [2,6,9])
ソート結果: [ 1, 2, 6, 7, 9 ]
------------------------------------------
ソート前: [ 7, 1, 9, 2, 6 ]
ソート後: [ 1, 2, 6, 7, 9 ]