합병 정렬(Merge Sort)

References

이번 글은 아래 자료들을 참고하여 작성하였습니다.
Section 33. Ack, MergeSort!
Merge Sort on Khan Academy

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }

  const center = Math.floor(arr.length / 2);
  const left = arr.slice(0, center);
  const right = arr.slice(center);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const results = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }

  return [...results, ...left, ...right];
}

위 그림에서 보듯 재귀함수 mergeSort Function을 거쳐서 주어진 배열의 길이가 1이 될 때까지 left, right로 쪼갠다. 쪼개진 값들을 merge Function을 거치면서 배열 left와 배열 right의 첫 값을 비교하여 작은 값을 왼쪽으로 몰고, 큰 값을 오른쪽으로 보낸다. 위 과정을 모두 거치면 주어진 배열이 오름차순으로 정렬된다.