CH04 : Sorting 2 - Merge Sort

 Merge sort는 sorting(정렬) 문제의 optimal 알고리즘으로, $O \left(n \log n\right)$ time을 필요로 한다.

Merge에 대하여 - 정렬된 sequences의 merge

Merge 문제

 오름차순으로 정렬된 sequence A, B에 대하여, A, B를 합하여 하나의 정렬된 sequence C를 만들어라. 

전략

 A의 첫 원소와 B의 첫 원소 중 최솟값으로 C의 첫 원소를 구한다. 이가 A의 원소였다고 가정하자. 그럼 문제는 A의 나머지 원소와 B의 원소를 merge하는 것으로 재정의된다. 

 만약 A 혹은 B가 empty하다면, 남은 배열의 원소들을 C의 뒷부분에 붙인다. 

A와 B의 merge --> C

Algorithm & Analysis 

Algorithm

merge(A, B, C)

//A or B가 empty
if (A is empty)
	rest of C = rest of B
else if (B is empty)
	rest of C = rest of A
    
//A, B 둘 다 not empty
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

Analysis

 Worst case는 배열의 원소가 번갈아가며 merge되는 경우로, 원소 간 비교연산(basic ops)가 n-1번 수행된다. 따라서 W(n)= n-1

Merge Sort

전략

 하나의 배열을 divide and conquer 전략을 활용하여 나누고, merge를 활용해 conquer한다. 

• 각 sequence가 1이 될 때까지 divide한다. 
  • 원소가 1인 sequence 각각은 정렬된 sequence이다.
• 이후 두 sequence끼리 merge한다. 
  • conquer와 merge를 동시 수행

Algorithm & Analysis 

Algorithm

• input : 첫 index가 first, 마지막 index가 last인 배열 E
  • 처음 시작할 때는 first를 0, last를 n-1로 설정
• output : 정렬된 배열 E

void mergeSort(Element[] E, int first, int last)

//recursive case
if (first<last)
    int mid = (first+last)/2
    mergeSort(E, first, mid) //왼쪽 subtree
    mergeSort(E, mid+1, last) //오른쪽 subtree
    merge(E, first, mid, last) //visit함수
    
//base case
return

• postorder traversal 형태를 보인다.

Analysis

 $W(n) = W \left( \frac{n}{2} \right) + W \left( \frac{n}{2} \right) + W_{merge} \left(n \right)\in \theta (n \log n) $

• 각각은 왼쪽 절반을 정렬하는 비용 + 오른쪽 절반을 정렬하는 비용 + merge하는 비용

 (merge sort 전략 부분의 사진 참고) 각 merge는 O(n) time이 소요되고, height $h = \log n$이므로 $W\left(n \right) = O(n \log n)$.

• height의 경우, h라 할 때, $n \times \left ( \frac{1}{2} \right) ^h = 1$에 따라 $h = \log n$이 된다. 

 (merge에 대하여 analysis 부분 참고) $W_{merge}(n) = n-1$

 따라서 $W(n) = n \log n$

 추가로, base case에 대하여, W(1)=0이다.