[JS 알고리즘] 병합 정렬(Merge sort)

• 이전에 살펴본 버블 정렬, 선택 정렬, 삽입 정렬 은 확장성이 좋지 않다. 예를 들어, 이러한 알고리즘으로 10만 개 정도 요소가 있는 배열을 정렬하려면 시간이 많이 걸린다.
• 큰 배열을 더 빨리 정렬하기 위해서는 합병 정렬, 퀵 정렬, 지수 정렬 등의 알고리즘을 사용할 수 있다.
  • 시간복잡도를 O(n logn)까지 개선할 수 있다.

병합 정렬 원리

병합 정렬은 1945년 컴퓨터공학자이자 수학자인 존 폰 노이만에 의해 개발됐다. 분할 정복 알고리즘 중 하나다.

• 병합과 정렬 을 조합한 알고리즘이다.
• 요소가 0개 또는 1개인 배열이 항상 정렬된다는 사실을 이용한다.
• 배열을 0개 또는 1개의 요소로만 구성된 더 작은 배열로 분해한 다음, 새로 정렬된 배열을 만든다. (divide and conquer)
• 즉, 일단 계속 쪼개서 배열을 0개나 1개의 요소로만 이뤄진 작은 배열을 만들고, 그 작은 배열들을 다시 합치며 정렬하는 과정을 끝까지 반복한다.

배열을 병합하는 헬퍼 함수

• 병합 정렬을 구현하려면 먼저 두 개의 정렬된 배열을 병합하는 기능부터 구현한다.(매개변수는 각각 정렬된 배열이다)
• 정렬된 두 개의 배열이 주어지면 위에서 만든 헬퍼 함수로 정렬된 새 배열을 반환한다.
  • 이 함수는 O(n + m)  시간복잡도와 O(n + m)  공간복잡도로 실행된다(n과 m은 입력하는 배열각각의 크기이다). 그리고 전달된 매개변수를 수정해서는 안된다.

- 빈 배열을 만들고 각 입력 배열에서 가장 작은 값들을 살펴본다.
- 첫번째 배열에 있는 i번째 요소를 두번째 배열의 j번째 요소와 비교한다.
    - 만약 첫번째 배열의 요소가 더 작다면, 첫번째 배열의 요소를 나중에 반환할 배열에 push하고, 첫번째 배열의 다음 요소로 이동한다.
    - 만약 첫번째 배열의 요소가 더 크다면, 두번째 배열의 요소를 나중에 반환할 배열에 push하고, 두번째 배열의 다음 값으로 이동한다.
- 위 과정을 반복하다가 하나의 배열을 소진하면, 다른 배열의 나머지 요소들을 모두 push한다.

• 배열을 병합하는 헬퍼 함수 코드

function mergeArray(array1, array2) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < array1.length && j < array2.length) {
    if (array1[i] < array2[j]) {
      result.push(array1[i]);
      i++;
    } else {
      result.push(array2[j]);
      j++;
    }
  }
  if (i === array1.length) return result.concat(array2.slice(j));
  if (j === array2.length) return result.concat(array1.slice(i));
}

console.log(mergeSort([1, 3, 7, 9, 11], [2, 6, 10, 16, 17, 18, 19, 20]));

병합 정렬 의사 코드

재귀형 코드이다.

• 비어 있거나 하나의 요소만 있는 배열이 될 때까지 배열을 반으로 나눈다
  • (slice 사용, 재귀).
• 아까 작게 나눈 배열들을 원본 배열의 길이로 돌아올 때까지 서로 병합한다.
  • (정렬된 배열을 합치는 헬퍼 함수 활용).
• 배열이 모두 병합되면 병합된 배열을 반환한다.

병합 정렬 자바스크립트 코드

function merge(array1, array2) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < array1.length && j < array2.length) {
    if (array1[i] < array2[j]) {
      result.push(array1[i]);
      i++;
    } else {
      result.push(array2[j]);
      j++;
    }
  }
  if (i === array1.length) return result.concat(array2.slice(j));
  if (j === array2.length) return result.concat(array1.slice(i));
}

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([10,24,76,73]));

병합 정렬의 성능

• 시간 복잡도(Best case, worst case, average case 모두) : $O(nlogn)$
  • log n : n개의 요소를 지닌 배열을 1개 이하의 요소만 지닌 배열들로 나누기 위해서는 $log_2n$ 번의 과정이 필요하다. (ex 8개 요소를 지닌 배열을 1개 요소만 지닌 배열들로 나누려면, 8→4→2→1처럼 $log_28$(=3) 번의 과정 필요) - 재귀
  • n : 최소단위로 나눈 배열들을 다시 합칠 때는 n 번의 비교를 해야한다. (위에서 merge함수)
    • (ex, 배열에 8개의 요소가 있다면, 병합을 위해서 대략 8번의 비교를 해야 한다)
  • 위 작업들이 함께 연달아 수행되므로, $O(nlogn)$ 의 시간 복잡도를 가지게 된다.
  • 병합 정렬은 어떤 데이터에서도 적용 가능하면서 가장 빠른 편인 정렬 알고리즘이다.
• 공간 복잡도 : $O(n)$
  • 병합 정렬의 공간 복잡도는 O(n)인데, 이는 배열이 커질수록 메모리에 저장해야 하는 배열의 개수가 많아짐을 뜻한다. (참고로 버블정렬의 공간복잡도는 상수였다.) 병합 정렬은 버블 정렬 등 앞에서 살펴본 다른 정렬 알고리즘에 비하면 더 많은 공간을 점유한다.