deftopDownMergeRun(arr, a, b):
clone = arr[a:b+1]
topDownMerge(clone)
arr[a:b+1] = clone
deftopDownMerge(arr):
iflen(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
topDownMerge(L)
topDownMerge(R)
i = j = k = 0while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+=1else:
arr[k] = R[j]
j+=1
k+=1while i < len(L):
arr[k] = L[i]
i+=1
k+=1while j < len(R):
arr[k] = R[j]
j+=1
k+=1
다음 코드는 Bottom-up merge sort를 파이썬에서 구현한 것이다.
defbottomUpMergeRun(arr, a, b):
clone = arr[a:b+1]
bottomUpMerge(clone)
arr[a:b+1] = clone
defbottomUpMerge(arr):
current_size = 1while current_size < len(arr) - 1:
left = 0while left < len(arr)-1:
mid = left + current_size - 1
right = ((2 * current_size + left - 1, len(arr) - 1)[2 * current_size + left - 1 > len(arr)-1])
merge(arr, left, mid, right)
left = left + current_size*2
current_size = 2 * current_size
defmerge(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2
for i inrange(0, n1):
L[i] = a[l + i]
for i inrange(0, n2):
R[i] = a[m + i + 1]
i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] > R[j]:
a[k] = R[j]
j += 1else:
a[k] = L[i]
i += 1
k += 1while i < n1:
a[k] = L[i]
i += 1
k += 1while j < n2:
a[k] = R[j]
j += 1
k += 1
3. Discussion
병합 정렬의 아이디어는 외부 정렬 (External Sort)의 근간이 될 정도로 major한 알고리즘이다.
일정한 시간복잡도를 보장하지만 Auxiliary (보조배열)을 사용해야 한다는 단점이 있다. 이 때문에 callstack에 쌓이는 공간 외에도 O(n)의 공간을 추가로 사용한다.
물론 In-place하게 구현할 수는 있으나, 그 경우 시간복잡도가 O(n2)이 된다. 다음 코드는 in-place merge sort를 파이썬에서 구현한 것이다.
definPlaceMerge(arr, start, mid, end):
start2 = mid + 1if (arr[mid] <= arr[start2]):
returnwhile (start <= mid and start2 <= end):
if (arr[start] <= arr[start2]):
start += 1else:
value = arr[start2]
index = start2
while (index != start):
arr[index] = arr[index - 1]
index -= 1
arr[start] = value
start += 1
mid += 1
start2 += 1definPlaceMergeSort(arr, l, r):
if (l < r):
m = l + (r - l) // 2
inPlaceMergeSort(arr, l, m)
inPlaceMergeSort(arr, m + 1, r)
inPlaceMerge(arr, l, m, r)