Algorithm - 5. Merge Sort

합병 정렬은 분할정복(divide-and-conquer)에 기초한 정렬 알고리즘이다. 합병 정렬은 이전 포스트에서 이야기한 힙 정렬과 같이 O(N logN)에 수행된다.

---

merge sort

합병 정렬과 힙 정렬은 모두 비교에 기초한 정렬이다. 수행시간은 O(N logN)으로 같다.

하지만 합병 정렬은 외부의 우선순위 큐를 사용하지 않는다. 외부 메모리를 사용하지 않는다는 것이다. 물론 제자리 힙 정렬 방식을 사용하면 힙 정렬도 외부 메모리를 사용하지 않지만, 기본적으론 그렇다. 또한 합병 정렬은 데이터를 sequential하게 접근한다. 원소들이 저장된 물리적 순서를 그대로 따라간다는 것이다. 따라서 디스트나 자기테이프와 같이 순차적 데이터 저장매체에 합병 정렬의 사용이 매우 적절하며 CPU에 일시적으로 적재가 불가능한 대규모의 데이터에 합병 정렬을 적용하는 것이 전체 수행시간에 좋다.

Alg mergeSort(L)
	input list L
    output sorted list L

if(L.size() > 1){
	L1, L2 <- partition(L, n/2)
    mergeSort(L1)
    mergeSort(L2)
    L <- merge(L1, L2)
}
return

합병 정렬은 크게 3단계로 구성된다.

1. divide : 무순리스트 L을 n/2 원소를 가진 각각의 L1, L2로 쪼갠다.
2. recur : L1, L2를 각각 재귀적으로 정렬한다.
3. conquer : L1, L2를 합친다.

Alg merge(L1, L2)
	input sorted list L1, L2
    output sorted list L that union L1, L2

L <- empty list
while(!L1.isEmpty() & !L2.isEmpty()){	//L1, L2 모두 원소가 있을 때
	if(L1.get(1) <= L2.get(1)){
		L.add(L1.removeFirst())
    } else{
    	L.add(L2.removeFirst())
    }
}
while(!L1.isEmpty()){
	L.add(L1.removeFirst())
}
while(!L2.isEmpty()){
	L.add(L2.removeFirst())
}
return L

방법은 간단하다. 먼저 리턴할 리스트를 마련한다.

첫 while문은 L1과 L2 모두 원소가 있을 때까지 반복한다. L1, L2의 첫 원소를 비교해 원소를 빼서 리턴할 리스트에 add한다. 그러다 보면, 두 리스트 중 한 리스트가 isEmpty()에 걸리게 되는 순간이 온다.

그러면 첫 while문을 빠져 나와 L1과 L2 중 남아 있는 원소 전부를 리턴할 리스트에 add해준다.

합병 정렬 트리 도식화

merge sort의 수행 과정을 이진 트리로 도식화 하여 이해를 도와보자.

초기 8개의 원소를 partition()한다. 그러면 L1은 {6 1 8 2}가 될 것이고, L2는 {3 5 7 4}가 될 것이다. 그렇지만 L2는 한참 뒤에 쓰인다. 먼저 쪼개진 L1에 대해 mergeSort(L1)을 호출하게 되면 다시 partition을 거치게 된다.

결국 merge()의 첫 호출은 L1 = {6}, L2 = {1}을 대상으로 진행이 된다. merge의 결과는 {1, 6}으로 리턴이 될테고 이를 재귀적으로 쭉쭉 이어가면 전체는 정렬이 된 상태로 return 된다.

성능 분석

합병 정렬 트리 도식화에서 보았듯 이진 트리 형태를 취하기 때문에 트리의 전체 높이는 O(logN)이 된다.

어떠한 높이 i에 대해서 실행되는 시간은 O(N)이다. 따라서 merge sort의 전체 수행 시간은 O(logN)이다.

배열 구현 합병 정렬

리스트가 아닌 배열에 대해서도 merge sort가 가능하다.

Alg mergeSort(A, p, r)
	input array A[p...r]
    output sorted array A

if(p<r){
	q <- (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)
}
return

q는 p와 r의 중간 인덱스다. q를 얻은 후 p~q까지의 리스트와 q+1~r까지의 리스트를 mergeSort보낸다. 리턴해 sort되어 돌아오면 이 두 리스트를 merge(A, p, q, r)에 가서 합쳐준다.

Alg merge(A, p, q, r)
	input sorted array A[p...q], A[p+1...r]
    output sorted array A[p...r]

i, k <- p	//i, k는 첫 번째 리스트의 시작 인덱스
j <- q+1	//j는 두 번째 리스트의 시작 인덱스

while(i<=q & j<=r){		//i는 q를 넘지 않고 j는 r을 넘지 않을 때까지
	if(A[i] <= A[j]){
    	tmp[k++] <- A[i++]
    } else{
    	tmp[k++] <- A[j++]
    }
}
while(i <= q){				//첫 번째 리스트 남은 거 다 채워줌
	tmp[k++] <- A[i++]
}
while(j <= r){				//두 번째 리스트 남은 거 다 채워줌
	tmp[k++] <- A[j++]
}

for(k <- p to r){	//임시 리스트를 input 리스트에 싹 다 채워줌
	A[k] <- B[k]
}
return

i와 j는 각각 L1, L2의 원소들을 가리키며 전진할 것이다. k는 첫 번째 리스트의 시작으로 초기화하고 임시 리스트에 원소를 채면서 움직일 것이다.

위에서 설명한 것과 유사하게 3가지의 while문을 돌고 임시 리스트 tmp에 원소를 p~r까지 채운다.

마지막에 input 리스트에 임시 리스트의 원소를 채워준다.

---

참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.