병합정렬(mergeSort)

병합 정렬은 정렬하고 싶은 수열을 두 개의 수열로 분할해 갑니다. 더 이상 분할되지 않는 상태에 이르면 그룹들을 병합해 나갑니다.

병합할 때에는 정렬이 끝난 두 개의 수열을 병합해서 정렬이 끝난 하나의 수열로 만듭니다. 이것을 하나의 그룹이 될 때까지 반복합니다.

 ``

const merge = function (left, right) {
  let merged = [];
  let leftIdx = 0,
    rightIdx = 0;
  const size = left.length + right.length;

  for (let i = 0; i < size; i++) {
    if (leftIdx >= left.length) {
      merged.push(right[rightIdx]);
      rightIdx++;
    } else if (rightIdx >= right.length || left[leftIdx] <= right[rightIdx]) {
      merged.push(left[leftIdx]);
      leftIdx++;
    } else {
      merged.push(right[rightIdx]);
      rightIdx++;
    }
  }

  return merged;
};

const mergeSort = function (arr) {
  if (arr.length < 2) return arr;
  const middle = parseInt(arr.length / 2);
  const left = mergeSort(arr.slice(0, middle));
  const right = mergeSort(arr.slice(middle));
  const merged = merge(left, right);
  return merged;
};