[자료구조] 머지 소트(Merge Sort, 합병 정렬)

 

 

합병 정렬은 분할 정복(devide & conquer) 방법에 속하는 정렬 알고리즘이다. 문제를 쪼개서, 작게 나누고, 해결하는 방법이다. 어느 컴퓨터공학과든 자료 구조 시간에 이 머지 소트는 무조건 배우고 간다고 생각할 정도로 기본적인 알고리즘이라고 본다.

 

머지소트는 다음의 단계를 거친다.

1. 정렬되지 않은 리스트를 원소를 1개 가지는 N 개의 서브리스트로 나눈다. (N = 리스트의 길이). 나눌 때는 절반씩 쪼개게 된다.

2. 서브 리스트를 합치면서 정렬을 하고, 원소를 N개 가지는 1개의 리스트까지 합병한다.

 

 

 

합병 과정에서 어떻게 정렬하는지 살펴보면, 아래와 같이 합병 과정 중인 2개의 서브리스트가 있을 때 로직은 다음과 같다.

 

 

1. i와 J가 기리키는 숫자의 대소관계를 비교하고, 작은 숫자를 새로운 임시 리스트에 K번째 자리에 대입한다. (k = 0부터 시작)

2. i와 J 중에서 리스트에 대입한 포인터를 한 단계 뒤로 옮긴다. (i++ 또는 j++)

3. k를 한 자리 늘린다.

4. i와 J 중에서 서브 리스트의 마지막에 도달하기 전까지 1~3번을 반복한다.

 

 

5. 포인터가 어느 한 서브리스트의 끝까지 도달했으면, 남은 서브리스트의 원소를 모두 병합할 임시 리스트에 몰아 넣는다.

void TopDownMerge(B[], iBegin, iMiddle, iEnd, A[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

 

6. 새로 만든 임시 리스트를 원래 리스트로 copy한다. (아래 수도 코드 참고)

void CopyArray(B[], A[], n)
{
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

 

---

 

시간복잡도

머지 소트는 최선, 최악, 평균 모두 O(n log n)의 시간복잡도를 가지고 있다.

Split 과정에서 배열을 거의 절반에 가깝게 나누고, 이를 배열의 크기가 1이 될 때까지 반복하므로 Log n의 연산이 진행된다.

Merge 과정에서는 각 단계마다 n개의 원소를 비교하고 합치게 된다. O(n)의 시간이 소모되는데, 이 과정을 log n 단계(원 상태로 돌아가기 전까지)에 걸쳐 진행하기 때문에 전체적으로 O(n log n)의 시간 복잡도를 가지게 된다.

 

공간복잡도

 

Merge 과정에서 CopyArray에 필요한 임시 리스트만큼의 추가 메모리가 필요하므로 O(n)의 공간 복잡도를 가진다.

 

Stable?

 

Merge 과정에서 부분 리스트 원소의 순서를 유지해주기 때문에 stable하다.