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は安定ソートです。