병합 정렬

시간 복잡도: O(NlogN)

function mergeSort(arr) {
  // 배열의 길이가 1 이하이면 그대로 반환
  if (arr.length <= 1) {
    return arr;
  }

  // 배열을 반으로 나누기 위한 인덱스 계산
  const midIndex = Math.floor(arr.length / 2);

  // 배열을 반으로 나누기
  const leftArr = arr.slice(0, midIndex);
  const rightArr = arr.slice(midIndex);

  // 분할된 배열을 각각 재귀적으로 정렬
  const sortedLeftArr = mergeSort(leftArr);
  const sortedRightArr = mergeSort(rightArr);

  // 정렬된 배열을 병합
  return merge(sortedLeftArr, sortedRightArr);
}

function merge(leftArr, rightArr) {
  const result = [];

  // 두 배열 중 하나가 빌 때까지 반복
  while (leftArr.length && rightArr.length) {
    // 두 배열의 첫 번째 요소를 비교하여 작은 것을 결과 배열에 추가
    if (leftArr[0] < rightArr[0]) {
      result.push(leftArr.shift());
    } else {
      result.push(rightArr.shift());
    }
  }

  // 남은 요소를 결과 배열에 추가
  return [...result, ...leftArr, ...rightArr];
}