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

합병정렬이란

• 리스트를 2개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬하는 알고리즘.
• 정렬된 2개의 부분 리스트를 합하여 전체 리스트를 정렬한다.
• 합병정렬은 안정 정렬(Stable)에 속하며 분할 정복 알고리즘(Divide and conquer)의 한 종류이다.

분할정복이란? 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
분할 정복 방법은 대개 재귀호출을 이용하여 구현한다.

분할(Divide): 입력 배열을 같은 크기의 2개의 배열로 분할

정복(Conquer): 부분 배열을 정렬한다. 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할방법적용

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

---

 

합병정렬 구체적인 개념

• 추가적인 리스트가 필요하다
• 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
• 합병정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(Merge)하는 단계이다.

---

합병정렬 알고리즘 예제

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

---

합병정렬 알고리즘 C코드

# include <stdio.h>
# define MAX_SIZE 8
int sorted[MAX_SIZE]; // 추가적인 공간이 필요

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){
    if(list[i]<=list[j])
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  // 남아 있는 값들을 일괄 복사
  if(i>mid){
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];
  }
  // 남아 있는 값들을 일괄 복사
  else{
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(int list[], int left, int right){
  int mid;

  if(left<right){
    mid = (left+right)/2; // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
  }
}

int main(void){
  int i;
  int n = MAX_SIZE;
  int list[8] = {21, 10, 12, 20, 25, 13, 15, 22};

  // 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
  merge_sort(list, 0, n-1);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d ", list[i]);
  }
}

 

---

 

합병정렬 특징 및 시간복잡도

장점

• 안정적인 정렬방법, 데이터의 분포 영향을 덜 받는다.(정렬되는 시간은 동일)
• 만약 레코드를 연결리스트로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을정도로 작아진다.
• 인플레이스(in-place sorting)으로 구현할 수 있다.
• 따라서 크기가 큰 레코드를 정렬할 경우에 연결리스트를 사용하면, 어떤 방법보다 효율적이다.

단점

• 만약 레코드를 배열로 구성하면, 임시 배열이 필요하다.
• 제자리 정렬(in-place)이 아니게 된다.
• 레코드들의 크기가 큰 경우에는 이동회수가 많으므로 매우 큰 시간적 낭비를 초래한다.

---

합병정렬 시간복잡도

분할단계는 비교 연산과 이동연산이 수행되지 않는다.

합병단계는 아래 와 같다.

합병단계 비교 회수

• 크기 n인 리스트를 정확히 균등 분배하므로 log(n) 개의 패스
• 각 패스에서 리스트의 모든 레코드 n개를 비교하므로 n번의 비교 연산

이동회수는

• 레코드의 이동이 각 패스에서 2n번 발생하므로 전체 레코드의 이동은 2n*log(n)번 발생
• 레코드의 크기가 큰 경우에는 매우 큰 시간적 낭비 초래
• 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 매우 효율적

즉, T(n) = nlog₂n(비교) + 2nlog₂n(이동) = 3nlog₂n = O(nlog₂n)

---