[알고리즘] 병합 정렬(Merge Sort) - 코딩밥상

병합 정렬(Merge Sort)이란?

병합 정렬은 앞서 배운 퀵 정렬과 같이 분할 정복에 기반한 알고리즘으로 성능도 퀵 정렬만큼 우수합니다.

이는 직역한 그대로 '나누고 조건에 맞게 합치는' 알고리즘입니다.

 

간략하게 동작 방식을 정리하자면,

1. 정렬할 데이터를 반으로 나눈다
2. 나뉜 하위 데이터의 크기가 2 이상이면 이 하위 데이터에 대해 첫번째 과정(반으로 나눔)을 반복한다
3. 동일 데이터에서 나뉜 하위 데이터 둘을 병합하여 원래대로 하나의 데이터로 만든다. 단, 병합할 때 데이터의 원소는 정렬 기준에 따라 정렬한다 
4. 데이터가 원래대로 모두 하나가 될 때까지 세번째 과정(병합)을 반복한다.

이 병합 정렬을 구현할 때 두 하위 데이터를 병합하는 부분에 관심을 더욱 기울여야 합니다. 병합하는 과정이 성능을 좌우하기 때문입니다.

해당 정리 글에서는 정렬의 조건을 오름차순으로 정하고 예시를 들어보겠습니다.

먼저, 조건에 맞게 병합하는 과정은 이렇습니다.

-병합 할 두 데이터(배열)와 두 데이터를 합한 것만큼 비어 있는 데이터(공간)을 마련하고, 비교할 데이터 각각의 첫 번째 요소들을 비교하여 작은 요소를 순서대로 새 데이터에 추가합니다. 추가된 요소는 원래의 데이터에서 삭제됩니다.

 

ex)

int A = {1,4,5,6,8}

int B = {2,3,7,9}

int C[9]

 -A : 4, 5, 6, 8

 -B : 2, 3, 7, 9

 -C : 1

 

 -A : 4, 5, 6, 8

 -B : 3, 7, 9

 -C : 1, 2 

 

 -A : 4, 5, 6, 8

 -B : 7, 9

 -C : 1, 2, 3

 

...

 

-A : 

-B :

-C : 1, 2, 3, 4, 5, 6, 7, 8, 9

---

구현

분할 정복에 기반하여 설계된 모든 알고리즘은 재귀 호출을 이용하여 쉽게 구현할 수 있습니다.

병합 정렬 알고리즘을 구현하는 함수는 크게 세 가지 작업을 수행합니다.

첫 째로 데이터를 반으로 나누고, 두 번째로 반으로 나눈 데이터를 매개 변수로 삼아 스스로를 재귀 호출하며, 마지막으로 둘로 나눈 데이터를 다시 병합합니다.

void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex){
    int LeftIndex = StartIndex;
    int RightIndex = MiddleIndex + 1;
    int DestIndex = 0;
    
    int* Destination = (int*) malloc(sizeof(int) * (EndIndex-StartIndex+1));
    
    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){    //왼쪽에 데이터가 남았을 경우
        Destination[DestIndex++] = DataSet[LeftIndex++];
    }
    while(RightIndex <= EndIndex){    //오른쪽에 데이터가 남았을 경우
        Destination[DestIndex++] = DataSet[RightIndex++];
    }
}

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, EndIndex);
    
    Merge(DataSet, StartIndex, MiddleIndex, EndIndex);
}