BFE.devでのAI解答例 - JavaScript コーディング問題
41. Merge Sortを実装する

以下がJavaScriptのMerge Sort実装例です。

function mergeSort(arr) {
  // 配列の要素数が1以下の場合は並べ替え不要
  if (arr.length <= 1) {
    return arr;
  }

  // 配列を二つに分割する
  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  // 二つに分割した配列それぞれに再帰的にsort()を実行する
  const sortedLeftArr = mergeSort(leftArr);
  const sortedRightArr = mergeSort(rightArr);

  // 二つに分割した配列をマージする
  const mergedArr = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < sortedLeftArr.length && rightIndex < sortedRightArr.length) {
    if (sortedLeftArr[leftIndex] < sortedRightArr[rightIndex]) {
      mergedArr.push(sortedLeftArr[leftIndex]);
      leftIndex++;
    } else {
      mergedArr.push(sortedRightArr[rightIndex]);
      rightIndex++;
    }
  }

  return mergedArr.concat(sortedLeftArr.slice(leftIndex), sortedRightArr.slice(rightIndex));
}

const arr = [5, 3, 1, 4, 2];
console.log(mergeSort(arr)); // [1, 2, 3, 4, 5]

上記実装の時間複雑性はO(n log n)、空間複雑性はO(n)となります。また、Merge Sortは安定ソートです。