분할 정복으로 정렬을 완성해가는 알고리즘이다. 알고리즘은 분할, 병합의 두 단계를 재귀 호출하는 것으로 완성되어 꽤 단순하게 구현할 수 있다. 그 유명한 폰 노이만 박사가 만든 알고리즘이다.
1. 병합 정렬(Merge sort)의 개념
원리는 앞서 말한 분할 정복(Divide and Conquer)이다. 문제 전체를 부분으로 쪼개서 하위 문제의 해를 찾아 상위 문제의 해를 얻는 방식으로 정렬에 적용하면 전체 길이의 배열을 절반, 다시 절반, 반복하여 나눌 수 없는 상태의 크기로 만들고 정렬이 끝난 부분들을 합쳐 정렬을 점차적으로 완성해나간다.
이 일을 진행할 때 코드에서 구현해야 하는 것은 두 가지다. 먼저 "분할"하는 것이고 분할된 것을 바르게 "병합"하는 것이다. 언제 분할하며 언제 병합하는지도 중요한데, 정렬되지 않은 구간은 분할하며 정렬된 구간은 병합한다. 정렬 여부는 딱 두 가지로 확인한다. 길이가 1인 부분은 당연히 정렬이 완료된 것이다. 그리고 병합이 올바르게 끝났다면 도출된 부분은 역시 정렬이 완료된 것이다.
길이가 10인 정수 배열이 있다고 해보자. 10은 5/5로 나눌 수 있고, 5는 다시 3/2로 나눌 수 있다.(병합 정렬에서 전체가 홀수인 경우, 보통은 전반부의 크기가 1크게 하여 분할한다.) 3은 2/1로, 마지막으로 2는 1/1로 나뉜다.
이렇게 나누면 7과 3은 각각 정렬이 완료된 최소 부분이다. 따라서 여기서 최초의 병합을 실시한다. 병합은 작은 것이 먼저 오도록 한다. 자리를 바꾸어 3 7 순으로 병합하면 이 부분은 정렬이 완료되었다. 이 과정을 충분히 거쳐 [7, 3, 8, 1, 5]의 3/2 부분이 각각 병합이 완료되었다고 해보자. [3, 7, 8], [1, 5]로 두 부분이 병합되어야 한다.
두 부분의 인덱스는 0에서 출발한다. 더 작은 수를 새로운 부분의 맨 앞에 위치시킨다.
빠져나간 부분의 인덱스는 다음 칸으로 이동하고 각 인덱스를 비교해 다시 작은 값을 새로운 부분의 다음 칸에 위치시킨다.
인덱스가 한 부분의 크기를 벗어나면 나머지 한 부분의 남은 값은 순차적으로 새로운 부분에 끌어오면 새로운 부분의 병합이 완료된다.
이런 식으로 부분을 순차적으로 병합하여 전체 배열을 정렬할 수 있다.
2. 소스코드
이 과정을 간단히 코드로 구현하면 아래와 같다. 파이썬에서는 슬라이싱을 활용하면 후반부분의 크기가 더 크게 만들어진다.
def mergesort(arr):
if len(arr) == 1:
return arr
front = mergesort(arr[:len(arr)//2]) # 전반부 분할
back = mergesort(arr[len(arr)//2:]) # 후반부 분할
merged= []
f,b = 0,0 # 전반부와 후반부의 인덱스
while f < len(front) and b < len(back):
if front[f] < back[b]:
merged.append(front[f])
f += 1
else:
merged.append(back[b])
b += 1
merged += front[f:] # 전반부가 남은 경우 모두 합치기
merged += back[b:] # 후반부가 남은 경우 모두 합치기
return merged
arr = [7,3,8,1,5,2,4,6,9,0]
print(*arr)
print(*mergesort(arr))
# 결과
# 7 3 8 1 5 2 4 6 9 0
# 0 1 2 3 4 5 6 7 8 9
3. 효율성
분할 정복의 시간 복잡도는 보통 O(NlogN)이다. 병합 정렬도 마찬가지로 O(NlogN)의 시간 복잡도를 갖는다. 이는 어떤 상태의 배열이든 항상 같기 때문에 어지간한 정렬 방법(퀵, 버블, 선택, 삽입)이 최악의 경우 O(N2)의 시간 복잡도를 갖는 것에 비해 매우 쓸만한 방법이다. 하지만 병합 과정에서 똑같은 크기의 배열이 하나 더 필요하므로 한 번에 거대한 배열을 정렬할 경우, 메모리 면에서는 좋은 선택이 아니라고 볼 수 있다.
