[알고리즘] Mergesort (합병 정렬) 이론 간략 정리

단순 합병 문제:

두 시퀀스 A, B를 오름차순으로 주어진다고 할때, 두 시퀀스를 하나로 합병한, 정렬된 시퀀스 C를 구하라(C 크기 = n)

 

합병 전략:

A,B의 최소값 중 더 작은값을 C에 넣는데, 만약 최소값이 A 에 있다고 가정하면,

A의 최소값을 C에 넣고, A의 나머지와 B, 그리고 C 를 재귀적으로 함수를 호출하여

합병을 한다.(분할 정복)

 

합병 수도코드:

Merge(A,B,C)
	if(A is empty)
    	rest of C = rest of B
    else if(B is empty)
    	rest of C = rest of A
    else if (first of A <= first of B)
    	first of C = first of A
       	merge(rest of A, B, rest of C)
    else
    	first of C = first of B
        merge(A, rest of B, rest of C)
   	return

비어있다면 남은 시퀀스의 나머지 모두 C 뒤에 넣고,

아니라면, 둘이 비교하여 작은값을 넣고,

나머지들은 재귀함수의 인자로 넣어서 처리한다.

 

Worst-case : 둘이 번갈아가면서 비교하는 경우 가장 많은 비교연산을 수행한다. 이때, n개가 있고, 마지막 요소는 비교를 하지 않고 C의 마지막에 넣으면 되므로, n-1번 수행한다.

$\therefore W(n) = n - 1$ 

 

합병정렬 알고리즘:

정렬되지 않는 시퀀스 둘을 정렬된 시퀀스로 합병할때 사용한다.

시퀀스를 둘로 나누어서 각 시퀀스를 정렬한 후에 두 시퀀스를 합병하는 방식으로 분할정복 알고리즘을 이용하자.

요소가 1개면 정렬된거라 가정하고 합병을 수행한다.(위 수도코드 참조)

void mergeSort(Element[] E, int first, int last){
	if(first < last){
    	int mid = (first + last) / 2; // middle index
    	mergeSort(E, first, mid);  //L Sorting(Divide)
        mergeSort(E, mid+1, last); //G Sorting(Divide)
        merge(E, first, mid, last); // Conquer & Combine
    }
   	return;
}

mergesort 과정은 이진트리 형태로 볼 수 있는데,

각 depth 별로 수행하는 연산은 $O(n)$으로 수행하게 되고,

height가 k라고 하면, 가장 아래로 내려갔을때 요소는 1이고, 이진트리이기때문에 depth 당 1/2씩 크기가 줄기때문에

$n(\frac{1}{2})^k = 1 , n = 2^k$이라 볼 수 있다.

따라서 $k = log_2n$ 이므로

height는 $O(logn)$이라 볼 수 있기 때문에,

해당 알고리즘의 Worst case의 시간복잡도는 아래식으로 나타낼 수 있다.

$W(n) = W(n/2) + W(n/2) + W_{merge}(n) \in \theta (n\log n)$ <- height* (depth 별 연산 수) = $O(n\log n)$

$W_{merge}(n) = n-1 $ <- 위 수도코드 참조

$W(1) = 0$ <- 요소가 1개면 이미 정렬되었다고 가정