Mergesort

특징

• 폰 노이만 성님이 개발함.
• in-place 정렬이 아닌 대표적인 정렬 알고리즘.
  • 정렬된 결과가 저장될 리스트가 1개 더 필요하니까 배열 크기 만큼의 공간 n이 하나 더 있어야 하는 것인데…
  • 잘 짜면 n/2 만큼만 더 사용하도록 할 수도 있음.
• 외부 정렬도 가능 (메모리에 정렬 대상을 다 올려둘 필요 없이, 디스크에서 일부 가져와서 정렬하고 넣어두고 다시 일부 가져와서 정렬하고 반복하여 전체를 정렬하는 것이 가능함)

Mergesort 구현

• Top-down 구현 방식과 Bottom-up 구현 방식이 있음.
• 리스트를 끝까지 분할한 다음,
• 정렬된 두개의 배열의 맨 앞에서부터 시작하여 index를 하나 씩 증가시키면서 정렬된 1개의 리스트로 merge 하는 것이 아이디어.
  • 이를 Two Pointer 라고 부르기도 하는 듯
  • index 증가시켜가면서 비교하는거니까, 꼭 정렬된 두개의 배열이 아니라 n개의 배열을 사용해서도 가능하다. n-way merge sort.

mergeSort(A, p, r) {
if (p<r) {
q = int((p+r)/2)
mergeSort(A, p, q)
mergeSort(A, q+1, r)
MERGE(A, p, q, r)
}

• 다른 구현 방법?https://en.wikipedia.org/wiki/Merge_sort
  • 위 예제 코드는 Top-down이라 재귀로 위에서부터 recursive하게 시작되었지만
  • Bottom-up 방식은 재귀 사용하지 않고 iterative하게 index를 증가시켜가며 둘씩 짝지어서 정렬하면서 시작한다.

왜 Quicksort가 Mergesort 보다 더 빠른 경우가 있는가?

Merge sort는 보면, 일단 맨 끝 depth까지 쭉 내려가서 1+1 = 2 만들고, 다음 1+1 = 2 만들고 … 반복해서 전체를 2로 만든다음에 2+2 = 4 만들고, 다음 2+2 = 4 만들고… 해서 각 depth 마다 전체 배열을 1cycle 순회한다.

반면 Quick sort는 처음부터 끝까지 내려가는게 아니라, 첫 번째 depth에서부터 부터 한쪽 브랜치로 쭉 타고 내려가면서 정렬하는 방식이다. (DFS 처럼)

첫 번째 depth에서 전체를 대상으로 1cycle 순회하면서 정렬하고,

(pivot이 반을 잘 나눴다고 가정하자)

두 번째 depth에서는 왼쪽 1/2을 대상으로 1/2cycle 순회하면서 정렬, 세 번째 depth에서는 왼쪽 1/2*1/2을 대상으로 1/2*1/2cycle 순회하면서 정렬… 하기 때문에

지역성(Locality)의 혜택을 볼 수 있다. 즉, 작게는 캐시 히트율이 좋아지며 크게는 참조되는 메모리 페이지만 계속 참조되기 때문에 페이징 스왑이 덜 발생한다.

Quicksort는 내부 정렬만 가능, Mergesort는 외부 정렬도 가능한 것도 이러한 동작 방식 때문에 그렇다.

O(n lg n) 증명

Divide and Conquer 문제는 다 이런 식으로 증명하는 듯?

1. \(n\)개의 문제가 원래 문제의 \(1/b\)인 \(a\)개의 부분 문제로 분할된다고 가정하면 이들 부분 문제를 해결하는데는 \(aT(n/b)\) 시간이 걸린다. (여기서는 a,b = 2)
2. 문제를 분할하는데 \(D(n)\)시간이 걸린다.
3. 병합하여 원래 문제의 해를 만드는데 \(C(n)\)시간이 걸린다. 이로부터 다음 점화식을 얻을 수 있다. \[T(n)=\begin{cases} \Theta(1) & n \le c \ aT(n/b) + D(n) + C(n) & \text{ otherwise } \end{cases}\]