합병정렬 (Merge Sort)

합병 정렬(Merge Sort) 의 개념 요약

• 분할 정복 알고리즘 중 하나이다.
  • 분할 정복(divide and conquer) 방법 - 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식
    문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
    분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

구체적인 개념

합병 정렬은 다음의 단계들로 이루어진다.

 

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

 

합병 정렬의 과정

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

 

 

예제

→ 배열에 27,10,12,20,25,13,15,22 이 저장되어 있다고 가정하고 오름차순으로 정렬해 보자.

 

 

→ 2개의 정렬된 리스트를 합병(merge)하는 과정

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

 

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)
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {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\n", list[i]);
  }
}

 

 

특징

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

 

• 장점
  - 안정적인 정렬 방법이다. → 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
  - 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. → 제자리 정렬(in-place sorting)로 구현할 수 있다.
  - 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

 

안정성 & 제자리성

합병정렬 알고리즘으로 정렬을 하는 경우, 원소들의 본래 순서가 거의 유지된 채 정렬된다. 따라서 합병정렬은 안정정렬(Stable Sort)이다. 또한, 기존 배열 이외의 추가적인 메모리를 필요로 하므로 제자리 정렬(In-place sort)이 아니다. 

 

시간복잡도

합병 정렬의 시간 복잡도는 n개의 데이터를 가지고 logn단계를 거치기 때문에 O(nlogn)이 된다.

퀵 정렬은 비대칭으로 분할이 될 수 있기 때문에 O(n²)인 반면에

합병 정렬은 언제나 절반씩 분할이 되기 때문에 언제나 항상 O(nlogn)의 시간 복잡도를 가진다.