병합정렬 (Merge Sort)

병합정렬(Merge Sort)이란?

병합(merge)을 이용한 정렬 알고리즘이다.

 

그렇다면 병합은 무엇을 의미하는가?

두 개의 sorted list에서 각각의 키(list A의 key, list B의 key)의 대소를 비교하면서 새로운 병합된(merged) sorted list를 생성하는 것을 의미한다.

 

예를들어,

<1, 5, 6, 8> <1, 5, 6, 8> 를 병합한다고 치자.

<1, 5, 6, 8> <2, 4, 7, 9>	<1>
<   5, 6, 8> <2, 4, 7, 9>	<1, 2>
<   5, 6, 8> <   4, 7, 9>	<1, 2, 4>
<   5, 6, 8> <      7, 9>	<1, 2, 4, 5>
<      6, 8> <      7, 9>	<1, 2, 4, 5, 6>
<         8> <      7, 9>	<1, 2, 4, 5, 6, 7>
<         8> <         9>	<1, 2, 4, 5, 6, 7, 8>
<           > <         9>	<1, 2, 4, 5, 6, 7, 8, 9>

위처럼 작은 key를 우선으로 하여 새로운 list 맨 뒤에 추가해주는 과정을 병합이라고 한다.

 

병합(Merge)과정을 pseudo code로 나타내면 다음과 같다.

Merge(A, p, q, r)
	n1 = q - p + 1 //n1은 array L의 크기
	n2 = r - q //n2는 array R의 크기
    
	L[1... n1 + 1]과 R[1... n2+1]을 새로운 배열로 선언해주기
    	for i = 1 to n1 
    		L[i] = A[p + i - 1] //값 채워주기
    	for j = 1 to n2 
        	R[j] = A[q + j] //값 채워주기
            
        L[n1 + 1] = 10000000000000 //각 배열의 마지막 값을 가장 큰 값으로 채워주기
        R[n2 + 1] = 10000000000000
        
        i = 1 //L의 index
        j = 1 //R의 index
        
        for k = p to r
        	if L[i] <= R[j] //compare
            	//move
                A[k] = L[i] // 비교해서 L이 R보다 더 작은 경우 새로운 배열에 넣어주기
                i = i + 1
                
            else
            	A[k] = R[j] // 비교해서 R이 L보다 더 작은 경우 새로운 배열에 넣어주기
            	j = j + 1

---

 

병합의 Running Time

n1과 n2가 각각 배열 L, R의 크기이므로 병합의 running time은 다음과 같다.

 $$\theta{(n_{1}+n_{2})}$$

 

 

병합(merge)의 주요 operation

1. compare

2. move

 

 

##기억해두어야 할 특징들

 

• compare의 횟수 ≤ move의 횟수 (모든 move 가 comparison 다음에 오기 때문이다.)
• move의 횟수 = n1 + n2
• compare의 횟수 ≤ n1 + n2 (= movement의 횟수)
• compare 횟수 + movement 횟수 ≤ 2(n1 + n2)

이를 종합하여 시간복잡도로 표현하면 다음과 같다.

$$\theta{(n_{1}+n_{2})}$$

---

병합에 대한 이해를 토대로, 병합정렬의 구성을 정리하면 다음과 같다.

 

병합정렬(Merge sort) 이란

1. Divide
n개의 key로 구성된 배열을 n/2 개의 key로 구성된 2개의 배열로 나눈다.

2. Conquer
merge를 사용하여, 두 개의 sorted list를 재귀적으로(recursively) 정렬한다.

3. Combine
정렬한 두 개의 list를 병합한다.

 

 

예를 들어서 merge sort를 이해해보자.

 

위와 같이 리스트를 divide 해준다.

 

더이상 리스트를 나눌 수 없을때, 두 리스트를 정렬해서 병합하는 것을 재귀적으로 수행한다.

 

 

 

위의 merge sort를 pseudo code로 표현하면 다음과 같이 쓸 수 있다.

 

MergeSort(A, p, r)
	if p < r // recursion되어 p = r, 즉 A의 길이가 1이 될 경우 코드가 중단되도록 한다.
    
    	q = |(p + r) / 2| //division
        MergeSort(A, p, q) //왼쪽 conquer
        MergeSort(A, q+1, r) //오른쪽 conquer
        Merge(A, p, q, r) //combine

---

Merge Sort의 Running Time

 

merge sort의 구성에 따른 running time은 다음과 같다.

1. Divide
$$\theta(1)$$
두 개로 나누기 위해 array의 가운데 지점을 찾는 연산만 필요하므로, 고정된 시간만 소요된다.

2. Conquer
$$2T({n\over2})$$
*여기서 T(n)은 n개의 element의 merge sort running time이다. 아래에서 좀 더 자세하게 다룰 것이다.

3. Combine
$$\theta(n)$$
위에서 (Merge 과정 참고)  n/2 크기의 배열 2개를 병합하는데 theta(n)만큼의 시간이 소요된다는 것을 보였으므로
combine 과정에서의 running time은 위와 같다.

 

T(n)을 재귀로 이해하기 (recurrence)

 

T(n)은 재귀로서 다음과 같이 표기할 수 있다.

$$\begin{align} T(n) = \theta{(1)} \\ (if  \ n = 1), \\ \\ 2T({n\over2}) + \theta{(n)} \\ (if \ n>1 \end{align})$$

n = 1일 때는 merging과정 (divide, conquer, combine)이 필요가 없기 때문에 위와 같은 시간이 걸리고,

n > 1 일 때는 세 단계를 합해준 만큼의 시간이 걸린다.

 

 

여기서, divide와 combine step에서의 element를 다루는 시간을 c로 하여 다시 나타내면 다음과 같다.

$$\begin{align} T(n) = c \\ (if  \ n = 1), \\ \\ 2T({n\over2}) + cn \\ (if \ n>1) \end{align}$$

 

T(n)을 recursion tree로 표현하면 조금 더 잘 이해할 수 있다.

이 tree를 다 합하면 T(n)이다.

 

수식으로 표현하면 아래와 같은 식이 나온다.

$$T(n) = 2T({n\over2}) +cn$$
$$T(n/2) = 2T({n\over4}) +cn$$
$$T(n/4) = 2T({n\over8}) +cn$$

 

tree의 각 level별로 합하면 모두 cn이 되고, tree의 level은 0부터 lg(n)까지 있으므로 이를 모두 합하면 아래와 같이 계산된다.

$$\begin{align}T(n) =  cn·(lg(n)+1) \\ = cn·lg(n)+cn \\ = \theta(nlg(n)) \end{align}$$

 

이 시간복잡도는 best case와 worst case 모두에 해당함을 기억하자.

 

 

---

다른 알고리즘과 시간복잡도, 공간고정여부 비교해보기

	Best Case	Worst Case	Sorted
Insertion Sort	$$\theta(n^{2})$$	$$\theta(n)$$	in place (n+c space)
Merge Sort	$$\theta(nlg(n))$$	$$\theta(nlg(n))$$	Not in place
Selection Sort	$$\theta(n^{2})$$	$$\theta(n^{2})$$	in place

* 공간고정여부에서 sorted in place에 해당하는 경우, space가 고정되어 있는 것을 의미하고,

not sorted in place 에 해당하는 알고리즘의 경우 space가 고정되어 있지 않다.

여기서 Merge Sort는 L, R array를 만들어야 하기 때문에 space가 고정되어 있지 않다.

 

* selection sort의 경우 (minimum selection 과 maximum selection이 있다.), 가장 작거나 큰 element를 찾아 제일 앞의 element와 swap하는 방식으로 정렬하는 알고리즘이다.

 

---

참고

Binary Search

- sorted list에서 특정 수 찾기. 가운데 수보다 큰지 작은지 비교하면서 recursive 하게 내려간다.

- T(n) = theta(lg(n))이다.