병합정렬 with 재귀함수

=> 병합정렬은 합병정렬이라고도 불리며 그 놀라운 수학자 존 폰 노이만이 만든 알고리즘이다. 어떠한 경우에도 시간 복잡도가 크게 다르지 않은 안정 알고리즘이며 분할 정복 기법을 사용한다.

코드를 입력하세요
// 병합
function merge(a, b) {
  if (a.length === 0) {
    return b;
  } else if (b.length === 0) {
    return a;
  } else {
    return [...a, ...b].sort((a, b) => a - b);
  }
  // } else if (a[0] >= b[0]) {
  //   return [b[0], ...merge(a, b.slice(1))];
  // } else if (a[0] < b[0]) {
  //   return [a[0], ...merge(b, a.slice(1))];
  // }
}

// 분할
function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  } else {
    const mid = Math.floor(arr.length / 2);
    return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
  }
}

// console.log([10, 12, 13, 15, 20, 21, 22, 25]);
console.log(mergeSort([21, 10, 12, 20, 25, 13, 15, 22]));

=> 나누는 부분과 합치는 부분을 재귀함수로 구현할 수 있다. 나눌 때 로직은 가운데를 찾아서 계속 재귀 인자로 넣어준다. 분해가 다 끝나면 merge함수로 인해 조합되는데, 합칠 때마다 정렬을 계속 해준다.