병합정렬 (Merge Sort)

- 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식

분할과 정복, 재귀호출, 시간복잡도 O(nlogn), 공간복잡도 O(n), 안전 정렬 알고리즘

 

#정의: 리스트를 두개로 나누어 각각을 정렬한 다음 다시 하나로 합치는 정렬방법

#정렬과정

1. 정렬할 데이터 집합을 반으로 나눔

2. 나누어진 하위 데이터 집합의 크기가 2 이상이면 이 하위 데이터 집합에 대해 1번을 반복

3. 하위 데이터 집합들을 다시 병합하면서 집합의 원소를 정렬함

4. 데이터 집합이 하나가 될때까지 3번을 반복하면 정렬이 완료됨

 

 

 

 

 

https://www.youtube.com/embed/XaqR3G_NVoo

Merge-sort with Transylvanian-saxon (German) folk dance - YouTube

 

3. 병합정렬의 주어진 소스 구현

 

int main( void ) {     int DataSet[] = {334, 6, 4, 2, 3, 1, 5, 117, 12, 34};     int Length = sizeof DataSet / sizeof DataSet[0];        int i = 0;     MergeSort( DataSet, 0, Length-1 );     for ( i=0; i<Length; i++ )  {         printf("%d ", DataSet[i]);     }     printf("\n");     return 0; } /* 분할함수 */ void MergeSort(int DataSet[], int StartIndex, int EndIndex) // 주어진 배열을 두개로 나눔 {     int MiddleIndex;     if ( EndIndex - StartIndex < 1 )         return;     MiddleIndex = (StartIndex + EndIndex) / 2;         // 중간값 설정     MergeSort( DataSet, StartIndex,    MiddleIndex );   // 왼쪽 배열 분할     MergeSort( DataSet, MiddleIndex+1, EndIndex );     // 오른쪽 배열 분할     Merge( DataSet, StartIndex, MiddleIndex, EndIndex );  // 분할된 배열 병합 } /* 병합함수 */ void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex ) {     int i;     int LeftIndex  = StartIndex;         // 좌측 배열 인덱스     int RightIndex = MiddleIndex + 1;   // 우측 배열 인덱스     int DestIndex  = 0;                // 결과 배열의 인덱스     int* Destination = (int*) malloc( sizeof(int) * (EndIndex - StartIndex + 1) ); // 임시 배열     // StartIndex 부터 MiddleIndex 까지의 배열과 MiddleIndex +1부터 EndIndex 까지의 배열을 비교 // 두 배열 중 작은 숫자를 찾아 임시 배열에 넣고 둘 중 어느 하나의 끝에 도달시 종료     while ( LeftIndex <= MiddleIndex && RightIndex <= EndIndex )     {                if (DataSet[ LeftIndex ] < DataSet [RightIndex ])         {                          Destination[ DestIndex ] = DataSet[ LeftIndex ];                          LeftIndex++;                } else {                          Destination[ DestIndex ] = DataSet[ RightIndex];                          RightIndex++;                }                DestIndex++;     } while ( LeftIndex <= MiddleIndex )   // LeftIndex 블록의 index가 아직 남아있을 경우     Destination[ DestIndex++ ] = DataSet[ LeftIndex++ ];     while ( RightIndex <= EndIndex )    // RightIndex 블록의 index가 아직 남아있을 경우         Destination[ DestIndex++ ] = DataSet[ RightIndex++ ];     DestIndex = 0;     for (i = StartIndex; i<=EndIndex; i++)     {                DataSet[i] = Destination[ DestIndex++ ]; // 임시 배열에서 원래 배열로 데이터 넣기     }     free( Destination ); }

 

 

4. 병합정렬 분석

 

구분	설명
비교	- 원소의 개수가 각각 m, n인 두 배열을 합병하기 위하여는 최악의 경우에 m+n-1회의 비교 - 두 부분 배열의 크기가 같고 이를 m이라 할 때, 최악의 경우에 2m-1회의 비교
시간복잡도	- n개의 원소로 구성된 배열에 병합 정렬을 적용하면 그 실행 시간은 n/2개의 원소로 된 두 개의 부분 배열을 정렬하는 시간과 이들을 합병하는 데 드는 시간의 합으로 O(nlogn)
안정성	- 병합 정렬에서는 동일한 두 키의 상대 위치가 정렬 과정에서 변하지 않으므로 안정적이나, 합병하는 과정에서 입력 배열의 크기만큼의 메모리 공간이 요구되므로 제자리 정렬은 아님
단점	- 최악의 경우의 실행시간이 이지만 각 부분배열을 합병 과정에서 합병된 결과가 배열 B에서    배열 A로 항상 복사되어야 하는 단점
활용	- 외부정렬에 주로 활용됨

 

 

 

머지 소트의 일반적인 구현은 in-place 정렬을 하지 않고 다른 메모리를 빌어 정렬 후 원래 리스트에 그 결과를 저장한다.

그래서 입력 크기 만큼의 메모리가 반드시 할당되어져 있어야 정렬 결과를 저장할 수 있다.

즉, 머지 소트는 n개의 개체가 있다면 O(n)만큼의 추가 공간이 필요한 것이다.

 

이런 경우에는 일반적으로 힙 소트 같은 알고리즘을 쓰는 것이 좀 더 원활한 성능과 구현의 간편함을 이끌어 낼 수 있다.

 

하지만, 정렬시 추가적인 공간을 사용함으로써 같은 값을 가지는 원소의 상대적인 순서를 유지한다는 장점을 가진다.

정렬을 stable과 unstable sorting으로 나눌 수 있는데 stable sorting이라 함은, 정렬 알고리즘이 같은 키가 (초기에 주어진 것처럼) 정렬 결과에서도 상대적으로 같은 순서를 유지하는 것을 말한다.

 

 

머지 소트는 평균적으로나 최악의 경우에나 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 순이라고 할 수 있다.