병합 정렬 (merge sort) 자료구조


퀵 소트의 최대 문제는 최악의 경우 O(n^2)의 복잡도를 가진다는 사실이다. 

이것은 분할 과정을 제어하기가 그리 쉽지 않기 때문이다. 
Pivot을 선택하는 다른 방법이 분할 과정의 결과를 공평하게 만들고자 시도했으나, 이러한 시도는 배열을 거의 유사한 크기의 부분 배열로 분할하지 못했다. 

이에 다른 전략이 나왔는데, 분할을 될 수 있으면 간단하고 단순하게 만들고 각기 정렬된 배열을 잘 병합하는데 초점을 둔 머지 소트가 나오게 되었다. 
컴퓨터 상에서 처음으로 사용된 알고리즘 중의 하나였으며 1945년 John von Neumann에 의해 개발되었다.


1. 알고리즘

머지 소트는 O(n(log n))의 정렬 알고리즘이며 divide-and-conquer 정책을 따르며 아래와 같이 동작한다.
  1. 정렬되지 않은 리스트를 반으로 두 개의 서브 리스트로 분할.
  2. 각 서브 리스트를 크기가 1이 될 때까지 recursive하게 분할 정렬한다.
  3. 분리된 서브 리스트들을 병합하여 원래 리스트로 복원시킨다.

아래는 간단한 의사코드이다.

  1. mergesort(data, first, last)
  2. {
  3.     if (first < last)
  4.     {
  5.          mid = (first + last) / 2;
  6.          mergesort(data, first, mid);
  7.          mergesort(data, mid+1, last);
  8.      
  9.          merge(data, first, last);
  10.     }


다음은 간단하게 구현된 머지 소트 코드이다.

  1. /* Sorts first n elements of array a[] in non-decreasing order. */
  2. template<typename T>
  3. void merge_sort(T a[]int n)
  4. {
  5.     int i, j, k;
  6.     T tmp;
  7.  
  8.     /* For small arrays, insertion sort is much faster */
  9.     if (< 16)
  10.     {
  11.         for (= 1; i < n; i++)
  12.         {
  13.             tmp = a[i];
  14.             for (= i 1; j >= 0 && tmp < a[j]; j--) a[1] = a[j];
  15.             a[1] = tmp;
  16.         }
  17.         return;
  18.     }
  19.  
  20.     int f = n / 2;  /* f = number of elements in first half */
  21.  
  22.     /* Recursively sort both halves */
  23.     merge_sort(a, f);
  24.     merge_sort(f, n f);
  25.  
  26.     /* Merge */
  27.     T *= new T[n]; /* temporary array to keep the sorted sequence */
  28.  
  29.     for (= 0, j = f, k = 0; i < f && j < n;)
  30.         s[k++] = (a[i] < a[j]) ? a[i++] : a[j++];
  31.  
  32.     while (< f) s[k++] = a[i++];
  33.     while (< n) s[k++] = a[j++];
  34.  
  35.     for (= 0; i < n; i++) a[i] = s[i];
  36.  
  37.     delete[] s;
  38. }


머지 소트의 일반적인 구현은 in-place 정렬을 하지 않고 다른 메모리를 빌어 정렬 후 원래 리스트에 그 결과를 저장한다.
그래서 입력 크기 만큼의 메모리가 반드시 할당되어져 있어야 정렬 결과를 저장할 수 있다.
즉, 머지 소트는 n개의 개체가 있다면 O(n)만큼의 추가 공간이 필요한 것이다.

물론 In-place 정렬을 할 수도 있지만 상당히 복잡하며, O(n(log n))의 복잡도로 동작한다 해도 실제로는 낮은 성능을 보여준다.
이런 경우에는 일반적으로 힙 소트 같은 알고리즘을 쓰는 것이 좀 더 원활한 성능과 구현의 간편함을 이끌어 낼 수 있다.

하지만, 정렬시 추가적인 공간을 사용함으로써 같은 값을 가지는 원소의 상대적인 순서를 유지한다는 장점을 가진다.
정렬을 stable과 unstable sorting으로 나눌 수 있는데 stable sorting이라 함은, 정렬 알고리즘이 같은 키가 (초기에 주어진 것처럼) 정렬 결과에서도 상대적으로 같은 순서를 유지하는 것을 말한다.

예) 다음과 같은 Person 객체의 벡터를 고려해보자.

첫번째 원소는 ["손승원", 48], 두번째 원소는 ["손승원", 31]과 같이 있다고 하고 이름순으로만 정렬을 한다.
일반적인 unstable sort의 경우는 두 원소의 순서가 바뀌지만, stable_sort는 비교 값이 같으므로 초기의 상대 순서를 유지하여 위치가 바뀌지 않는 것이다.


2. 성능


머지 소트는 평균적으로나 최악의 경우에나 O(n(log n))의 복잡도를 갖는다.
하지만 배열을 정렬하기 위해 힙 소트는 O(1)의 추가 공간이 필요하지만 머지 소트는 O(n)의 공간이 필요하다.
그리고 머지 소트는 실제 사용시 최악의 경우에 O(n^2)의 복잡도를 가지는 퀵 소트에 비해 성능이 떨어지며 힙 소트 보다도 느린 경우가 많다.

머지 소트는 종종 연결 리스트의 정렬에 최적의 선택이 되기도 한다.
(참고로, 제조사마다 다르긴 하지만, 대부분의 STL list::sort 함수는 머지 소트로 구현되어 있다)


배열을 머지 소트할 때는 O(n)의 추가 공간이 필요하지만 연결 리스트를 머지 소트시에는 O(1)의 추가 공간만 필요하다.
다가 연결 리스트의 느린 랜덤 억세스 성능이 다른 알고리즘으로는 정렬시 성능을 내지 못하도록 하거나(퀵 소트) 정렬 자체가 불가능하다 (힙 소트).

펄 5.8에서 머지 소트는 기본 정렬 알고리즘으로 채택되었으며, 자바에서는 리스트의 기본 정렬 방식으로 1) 머지 소트를 사용하거나 2) tuned depending on the datatypes 퀵 소트를 사용 + 개체수가 7개 이하일 때 삽입 정렬 방식을 사용한다.

결국
보편적인 환경에서 성능의 우위는 quick > heap > merge 순이라고 할 수 있다.



덧글

댓글 입력 영역