병합 정렬

이전까지 배운 정렬 알고리즘은 성능이 좋지 않다.

병합 정렬은 이전에 배운 정렬 알고리즘(버블 정렬, 삽입 정렬, 선택 정렬)의 시간 복잡도 O(n²)를 O(n log n)까지 줄일 수 있다. 병합 정렬은 큰 배열을 더 작은 하위 배열로 나누어 정렬하는 분할 정복(Divide and Conquer) 패턴을 사용한 정렬 방법이다.

    [8, 2, 6, 3, 7, 1, 4, 9]
		      ↓
  [8, 2, 6, 3] [7, 1, 4, 9]
		      ↓
  [8, 2] [6, 3] [7, 1] [4, 9]
              ↓
[8] [2] [6] [3] [7] [1] [4] [9]
              ↓
  [2, 8] [3, 6] [1, 7] [4, 9]
              ↓
   [2, 3, 6, 8] [1, 4, 7, 9]
              ↓
    [1, 2, 3, 4, 6, 7, 8, 9]

단일 요소를 가진 배열로만 이루어질 때까지 분할을 반복한다. 그리고 단일 요소로 이루어진 배열을 다시 정렬하며 병합한다. 그리고 정렬된 두 배열을 비교하여 마찬가지로 정렬된 형태로 병합한다. 그리고 모든 배열을 병합할 때까지 반복한다. 하나의 단계를 병합할 때는 시간복잡도가 그 단계의 숫자의 수, 즉 O(n)이 요구된다. n개의 숫자를 하나가 될 때까지 분할해 나가면 시간 복잡도는 O(log₂n)이 나온다.

즉, 이 패턴을 사용한 방식은 최고/최악 모두 O(n log n)이 나온다. 공간 복잡도도 O(n)으로 다른 정렬 방식(버블 정렬)보다 더 많은 공간을 요구한다.

/**
 *
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @returns number[]
 */
function merge(arr1, arr2) {
  let answer = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      answer.push(arr1[i]);
      i++;
    } else {
      answer.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    answer.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    answer.push(arr2[j]);
    j++;
  }

  return answer;
}

/**
 * @param {number[]} arr
 * @returns number[]
 */
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

console.log(mergeSort([1, 53, 23, 92, 54, 111]));