병합 정렬 / 합병 정렬 (Merge Sort)

"분할하여 정복한다" 흔히 "Divide and Conquer"라 알려져 있는 격언은 실제 정치에서 뿐만 아니라 알고리즘에서도 자주 사용하는 norm 입니다. 전체를 한 번에 다 아우르지 않고 다룰 수 있는 작은 부분으로 쪼개면 일이 훨씬 수월해지는 것은 당연한 이치입니다. 

이번 포스트에서 다룰 병합 정렬은 퀵 정렬과 더불어 정렬 알고리즘 중 대표적인 "분할 정복" 알고리즘입니다. 역사상 최고의 천재 중 손꼽히는 존 폰 노이만 (John Von Neumann) 이 무려 1945년에 고안한 알고리즘으로 최선/최악의 경우 일정하게 $O(n\log n)$의 시간 복잡도를 보장하는 알고리즘입니다. 한 번 예를 들어 살펴볼까요?

EXAMPLE

병합정렬은 크게 2 가지 스텝으로 이루어져 있습니다.

1. 분할 (Divide)

"분할 정복"의 첫 번째 단계입니다. 주어진 배열을 반으로 쪼개면서 원소가 1 개가 남을 때까지 (배열을 더 이상 나눌 수 없을 때까지) 계속 분할합니다. 

2. 정복 (Conquer) 

"분할 정복"의 두 번째 단계입니다. 최소한으로 분할된 부분 배열에 대해 합치는 과정으로 합칠 때마다 분할의 역방향으로 인접한 두 개의 배열에 대해 정렬하게 됩니다.

위의 예에서는 왼쪽의 [21], [10]이 합쳐지면서 정렬되어 [10,21] 배열을 return하고 다음 [12], [20]이 합쳐지면서 [12,20] 배열을 return합니다. 작은 부분부터 정렬되면서 합쳐지므로 최종적으로는 정렬이 완성된 배열이 완성되게 됩니다.

파이썬 코드

먼저 분할 쪽 코드부터 구상해 보겠습니다. 퀵정렬과 마찬가지로 배열을 더 이상 나눌 수 없을 때까지 분할하니 재귀를 사용하면서 원소의 개수가 1일 때 재귀를 종료하는 코드를 작성하면 될 것 같습니다. 그리고 마지막으로 최종 분할된 배열에 대해 merge를 해야겠죠? 

1. 분할

from typing import List

def merge_sort(List: array) -> List:
    ## 원소가 1개 남을 때 그 배열을 return
    if len(array) == 1:
        return array
        
    ## 반으로 계속 재귀적으로 분할
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    
    ## 최종적으로 return된 배열에 대해 merge
    ## 원소 1개 배열부터 합쳐가면서 최종적으로 정렬된 array return
    return merge(left_array, right_array)

 

2. 정복

그렇다면 정복 (정렬하면서 합병)쪽 코드는 어떻게 될까요? 위 코드의 "merge" 함수인데 파라미터로 분할된 left_array와 rigth_array를 받습니다. left_array와 right_array를 합칠 때 정렬을 해야되니 left_array와 right_array를 순차적으로 비교하면서 작은 값부터 어떠한 list에 append하는 방법을 생각해 볼 수 있을 것 같습니다. 이 때, left_array, right_array는 더 작은 단계에서 이미 각각 정렬되어 있습니다.

def merge(leftArray, rightArray):
    ## 정렬해서 합병할 최종 list
    result = []
    while len(leftArray) > 0 and len(rightArray) > 0:
        ## 매번 leftArray와 rightArray의 첫 번째 인덱스를 비교해서
        ## 작은 값부터 result 리스트에 append
        if leftArray[0] <= rightArray[0]:
            ## leftArray의 값이 더 작으므로 result에 pop하면서 append
            ## 배열을 deque로 받았을 시에는 leftArray.popleft()
            result.append(leftArray.pop(0))
        else:
            result.append(rightArray.pop(0))
            
    ## leftArray든 rightArray든 어느 한 배열이 원소가 남아있는 상황
    ## 각 배열은 이미 정렬된 상태이므로 그대로 추가
    if len(leftArray) > 0:
        result += leftArray
    elif len(rightArray) > 0:
        result += rightArray
        
    ## 최종 정렬된 result 리스트 return
    return result
            

위 그림의 정복 마지막 단계 [10,12,20,21]과 [13,15,22,25]에 대해 어떻게 동작하는지 살펴보겠습니다.

leftArray	rightArray	result
10,12,20,21	13,15,22,25
12,20,21	13,15,22,25	10
20,21	13,15,22,25	10,12
20,21	15,22,25	10,12,13
20,21	22,25	10,12,13,15
21	22,25	10,12,13,15,20
	22,25	10,12,13,15,20,21
		10,12,13,15,20,21,22,25

 

시간 복잡도

시간 복잡도는 어떻게 될까요? 아까 언급했듯이 매번 절반으로 배열을 분할하고 $O(\log n)$ 각 층마다 배열을 정렬하니 $O(n)$ 항상 안정적으로 $O(n\log n)$의 시간 복잡도가 소요됩니다. 퀵정렬 또한 최선의 경우 피벗이 매번 중앙을 분할하면 $O(n\log n)$의 시간이 소요되나 정렬되어 있는 배열의 경우 $O(n^2)$가 소요됩니다.

이처럼 안정적인 성능으로 아직까지 여러 라이브러리에서 현역으로 활동하고 있는 알고리즘이고 여담으로 파이썬의 sort 내장 함수는 퀵정렬과 병합정렬을 heuristic하게 합친 팀소트 (Tim Sort)가 사용됩니다.

공간 복잡도는 어떨까요? 위의 "정복" 부분 코드를 보면 합칠 배열을 저장할 result를 매번 선언합니다. 따라서 별도의 저장 공간이 $O(n\log n)$ 만큼 소요됩니다. 반대로 배열이 아닌 연결 리스트 (linked list)로 구현할 경우 기존 저장 공간에서 next head 포인터만 바꿔주면 되어 제자리 정렬 (in-place sort)이 가능합니다.

홍머스 정리

• 분할해서 정복하라
• 안정적으로 $O(n\log n)$

참조

• <파이썬 알고리즘 인터뷰>, p488
• ratsgo.github.io/data%20structure&algorithm/2017/10/03/mergesort/