マージソート

merge_sort.js

'use strict';

// 与えられた配列を昇順にマージソートでソートした配列を返す.
function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  }
  const mid = Math.floor(array.length / 2);
  const a = array.slice(0, mid); // array[0:mid]
  const b = array.slice(mid); // array[mid:]
  return merge(mergeSort(a), mergeSort(b));
}

// 2つの配列a, bの要素を小さい順に取り出して並べた配列を返す.
function merge(a, b) {
  const result = [];
  for (let i = 0, j = 0; i < a.length || j < b.length; ) {
    if (i === a.length) {
      result.push(b[j]);
      j++;
      continue;
    } else if (j === b.length) {
      result.push(a[i]);
      i++;
      continue;
    }
    if (a[i] <= b[j]) {
      result.push(a[i]);
      i++;
    } else {
      result.push(b[j]);
      j++;
    }
  }
  return result;
}

console.log('sorted', mergeSort([]));
console.log('sorted', mergeSort([1]));
console.log('sorted', mergeSort([2, 1]));
console.log('sorted', mergeSort([1, 3, 2]));
console.log('sorted', mergeSort([1, 2, 3]));
console.log('sorted', mergeSort([1, 3, 2, 3])); // 重複があるケース