- 주어진 문제를 둘 또는 여러 개의 작은 부분 문제들로 나누고, 이들을 각각 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략
- 이때 나뉜 부분 문제가 아직도 충분히 작지 않아 해결하기 어렵다면 분할 정복을 부분 문제에 다시 적용하면 됨
- 이때 보통 순환 호출이 사용됨
- 분할(divide): 주어진 문제를 같은 유형의 부분 문제들로 분할함
- 정복(conquer): 부분 문제들을 해결하여 결과(부분적인)를 만듦
- 병합(combine): 부분적인 결과들을 묶어 최종 결과를 만듦
- 분할 정복이 모든 문제에서 더 효율적인 것은 아님
- 그렇지만 정렬이나 탐색과 같은 많은 중요한 문제에서 상당한 효과를 발휘함
- 때로는 분할 정복을 축소 정복(decrease-and-conquer)과 구분하기도 함
- 축소 정복은 원래의 문제를 나눈 후에 해결해야 할 부분 문제가 하나만 남는 특별한 경우를 말함
- 정렬된 배열에서의 이진 탐색은 분할 정복 전략 중에서도 축소 정복을 이용하는 것임
- 입력 리스트를 균등하게 두 부분으로 나누고, 각각으로 정렬할 다음 결과를 병합함
- 물론, 부분 리스트가 처리하기에 충분히 작지 않으면 분할 과정을 반복함
- 병합 정렬은 입력 리스트를 같은 크기의 두 개의 부분 리스트로 '분할'함
- 이 과정은 부분 리스트의 크기가 1이 될 때까지 반복되는데, 크기가 1이면 그 부분 리스트는 이미 정렬된 것임
- 따라서 '정복' 단계에서 할 일은 없고, 병합 단계만 잘 처리하면 정렬이 끝남
- '병합'은 2개의 정렬된 리스트를 병합해 하나의 정렬된 리스트를 만드는 과정으로, 이를 반복하다 보면 최종적으로 하나의 정렬된 리스트를 얻게 됨
- 병합 정렬도 순환 구조로 간략하게 기술할 수 있음
def merge_sort(A, left, right): # A[left, ... , right]를 오름차순으로 정렬
if left < right: # 항목이 2개 이상인 경우
# 리스트를 균등하게 둘로 나누고, 왼쪽 부분(A[left~mid])과 오른쪽 부분(A[mid+1 ~ right])을 각각 병합 정렬
# 마지막으로 정렬된 두 부분 리스트를 병합함
mid = (left + right) // 2
merge_sort(A, left, mid)
merge_sort(A, mid+1, right)
merge(A, left, mid, right)
# else: 항목이 1개인 경우, 자동으로 정복되었음
- 병합 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 부분 리스트를 병합하는
merge()에서임
- 효율적인 병합을 위해서는 임시 리스트가 필요함
- 병합 과정은 각 부분 리스트의 첫 번째 요소(i=left, j=mid+1)부터 시작하고, 오른쪽으로 진행됨
- 두 부분 리스트의 요소 A[i]와 A[j]를 비교하여 더 작은 요소를 임시 리스트 sorted에 복사하고 인덱스를 증가시킴
- 이 과정은 리스트 하나의 모든 요소가 복사될 때까지 반복되고, 마지막으로 다른 리스트의 남은 요소들을 모두 임시 리스트로 복사하면 병합이 종료됨
def merge(A, left, mid, right):
k = left # 병합을 위한 임시 리스트의 인덱스
i = left # 왼쪽 리스트의 인덱스
j = mid + 1 # 오른쪽 리스트의 인덱스
while i<= mid and j <= right:
# 값이 작은 부분 리스트의 요소를 sorted에 복사하고, 그 리스트의 인덱스를 증가시킴
# 이 과정은 어느 한쪽 부분이 모두 처리될 때까지 진행
if A[i] <= A[j]:
sorted[k] = A[i]
i, k = i+1, k+1
else:
sorted[k] = A[j]
j, k = j+1, k+1
# 남은 부분 리스트의 모든 요소를 sorted로 복사
# 슬라이싱을 이용함
if i > mid:
sorted[k:k+right-j+1] = A[j:right+1]
else:
sorted[k:k+mid-i+1] = A[i:mid+1]
# 임시 리스트에 저장된 결과를 원래의 리스트 A에 복사
A[left:right+1] = sorted[left:right+1]
- 병합 정렬은 입력의 구성에 상관없이 동일한 차수의 연산을 함
- 따라서 최악·평균·최선을 나누어 생각할 필요가 없음
- 크기 $n$인 구간을 반으로 나누는 분할 트리의 높이는 $O(\log n)$ (밑을 적으면 $\lceil \log_2 n \rceil$에 가깝다고 보면 됨)
- 한 레벨(같은 깊이)에서 이루어지는 모든
merge를 합치면, 원소는 각각 최대 한 번씩만 임시 배열을 거치므로 그 레벨에서의 작업량은 $O(n)$
- 레벨 수 $\times$ 레벨당 $O(n)$이므로 시간 복잡도는 $O(n \log n)$임
- 순환식으로 쓰면 대개 $T(n) = 2T(n/2) + O(n)$, 마스터 정리(또는 전개)로 $T(n) = O(n \log n)$
- 추가로 길이 $n$과 같은 임시 배열을 쓰므로 공간은 배열 기준 $O(n)$
- 분할 정복의 대표 알고리즘으로 시간 복잡도 $O(n \log n)$을 갖는 매우 효율적인 정렬 방법임
- 입력의 구성과 상관없이 동일한 시간에 정렬되고, 안정성을 만족함
- 제자리 정렬이 아님
- 입력 리스트의 크기와 같은 크기의 임시 리스트가 반드시 있어야 함
- 병합 정렬에서 부분 리스트를 두 개 이상으로 나누고 결과를 병합할 수도 있음
- 이러한 방법을 다중(multiway) 병합 정렬이라고 하는데, 주 메모리보다 속도가 느린 보조 메모리에 있는 파일을 정렬하는 등의 응용에서 특히 유용하게 사용될 수 있음