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

병합 정렬이란?

‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법으로 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

병합 정렬 알고리즘

분할 ➡ 정복 ➡ 결합

• 분할(Divide)
  입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복(Conquer)
  부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine)
  정렬된 부분 배열들을 하나의 배열에 합병한다.

❓ 2개의 배열을 merge 하는 과정은?

1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
2. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

시간복잡도

평균 : O(nlog₂n)
최악 : O(nlog₂n)
최선 : O(nlog₂n)

❓ 퀵정렬보다 병합정렬이 유리한 경우가 있을까?

만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 합병 정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때, 사용하면 효율적이다. LinkedList를 퀵 정렬에 사용해 정렬하면 성능이 좋지 않다. 이유는 퀵 정렬은 순차 접근이 아닌 임의 접근이기 때문이다. LinkedList는 삽입과 삭제 연산에서는 유용하지만, 접근 연산에서는 비효율적이다.

👉 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.

병합정렬 예시

병합정렬 코드

function merge(left, right) {
  const sortedArr = [];
  
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  
  const boundary = Math.ceil(arr.length / 2);
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
  
  return merge(mergeSort(left), mergeSort(right));
}

✔ mergeSort(arr) 👉 배열을 반으로 나누어 주는 함수

✔ merge(left,right) 👉 반으로 나누어준 함수를 갖고 정렬해 새로운 배열로 만들어주는 함수