[JS] 재귀함수를 이용한 병합정렬

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.

---

오늘은 Divide and Conquer에서 자주 사용되는 재귀함수를 이용하여 merge sort를 구현해보도록 하겠습니다.

function mergeSort(arr) {
  // 입력된 배열의 길이가 1 이하이면 더 이상 재귀 호출을 하지 않습니다.
  if (arr.length <= 1) return arr;

  // 배열을 절반으로 잘라 두 개의 작은 배열로 분할하고,
  // 두 작은 배열에 대해 재귀 호출을 수행합니다.
  const slicer = Math.floor(arr.length / 2);
  const arr1 = mergeSort(arr.slice(0, slicer));
  const arr2 = mergeSort(arr.slice(slicer));

  // `arr1`, `arr2`는 **이미 정렬되어있는 상태**이므로,
  // 이 성질을 이용해 두 배열을 **정렬되어있는 큰 배열**로 합칠 수 있습니다.
  const newArr = [];
  for (let i = 0, j = 0; i < arr1.length || j < arr2.length; ) {
    if (arr1[i] == undefined || arr1[i] > arr2[j]) {
      newArr.push(arr2[j]);
      j++;
    } else {
      newArr.push(arr1[i]);
      i++;
    }
  }

  // 큰 배열을 반환합니다.
  return newArr;
}