[분할정복] 합병정렬(Merge Sort) 구현 및 시간복잡도 증명하기

분할정복

알고리즘 유형중에 분할정복 유형이 있다. 

문제를 부분 문제로 나누어 각 부분 문제를 해결하고, 부분 문제들의 결과를 합쳐 기본 문제를 해결하는 유형이다.

정렬 알고리즘에서 합병정렬과 퀵정렬이 이에 속하는데, 합병 정렬에 대해 알아보고자 한다.

 

합병정렬

https://www.geeksforgeeks.org/merge-sort/

크게 세 부분으로 생각하면 된다.

1. 나눈다.

2. 정복한다.

3. 합친다.

 

1. 나눈다.

리스트를 절반씩 나눈다. 이를 재귀적으로 실행하기 때문에 계속해서 절반씩 나누어진다.

그림에서 1~3번째 줄 과정이다.

 

2. 정복한다.

1.나눈다 와 같은 함수라고 보면 된다. 나누다가 길이가 1이 된다는 것은 더 이상 나눌 수 없을 뿐더러 '정렬'된 상태라는 것이다.

그러므로 이 때 결과를 return 한다.

그림에서 4번째, 가운데 과정이다.

 

3. 합친다.

1과 2를 마치고 나면 머지 함수로 정렬된 리스트를 만드는 과정이다. 리스트 두 개를 파라미터로 사용하여 반복문을 돌면서 두 리스트를 비교, 정렬하여 최종 정렬 리스트를 반환한다.

그림에서 5~7번째 줄 과정이다.

 

 

1, 2번 과정은 merge_sort(my_list) 함수로, 3번 과정은 merge(list1, list2) 함수로 구현한다.

먼저 merge_sort 과정을 보자.

def merge_sort(my_list):
    # base case - 길이가 0 또는 1이라면 정렬된것이므로 리턴
    if len(my_list) < 2:
        return my_list
      
    # recursive case - divide and conquer
    # my_list를 반씩 나눈다(divide)
    left_half = my_list[:len(my_list)//2]
    right_half = my_list[len(my_list)//2:]
    
    # 양쪽을 각각 정렬하기 위해 merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
    # merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
    return merge(merge_sort(left_half), merge_sort(right_half))
  
# 테스트
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))

처음 리스트가 들어오면 계속해서 절반씩 나눈다. 그리고 리턴문으로 머지소트 함수가 재귀로 실행되므로 다시 절반씩 나누고....

과정을 반복하다가 길이가 1이 되면 반환한다. 이 때 merge 함수가 실행되는데 인자로 각각 길이가 1인 좌측, 우측 요소가 생길 것이다.

 

그러면 merge 함수를 보자.

# 정렬된 리스트를 돌려주는 함수
def merge(list1, list2):
    i,j = 0, 0
    
    merged_list = []
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

    # (list1 끝나고) list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]
    # (list2 끝나고) list1에 남은 항목이 있으면 정렬 리스트에 추가
    if j == len(list2):
        merged_list += list1[i:]
            
    return merged_list

merge 함수는 길이가 1인 두 리스트를 받을 것이다. 

두 리스트의 인덱스를 각각 돌면서 merged_list (정렬된 리스트)를 만들어나갈 것이다.

이 때 어느 한쪽이 먼저 끝나면 다른 한 쪽을 merged_list에 추가해준다. 

 

다시 merge_sort 함수로 돌아와보자.

정렬된 리스트가 리턴되고, 다시 merge(merge_sort(left_half), merge_sort(right_half) , merge함수가 실행된다.

나눴던 횟수만큼 다시 merge 가 이루어진다.

 

최종적으로 하나의 merges_list가 반환된다.

 

시간 복잡도

병합 정렬의 시간 복잡도는 최악의 경우 O(N * logN) 이다. 

일반적으로는 퀵 정렬보다 느리지만, 퀵 정렬의 경우 최악 O(N ^ 2)기 때문에 병합 정렬이 보다 안정적이다.

 

 

그러면 그림을 보며 시간 복잡도를 증명해보자.

 

Khan Academy

 

정렬은 합치는 순간 실행되는데, 합치는 단계는 log_2(N) 이다.

즉, [38, 27, 43, 3, 9, 82, 10] 리스트가 있다면 길이가 1인 개별 배열에서 다시 머지해갈 때,

2개 x 4묶음 > 4개 x 2묶음 > 8개 x 1묶음 으로 총 깊이(merging time) 3 이다. 

즉, 데이터의 갯수가 N 개일 때 log_2(N) 이다.

 

그리고 매 단계에서 정렬 자체에 필요한 수행시간은 N이다.

N이 8이라면 1번씩 8번, 2번씩 4번, 4번씩 2번 비교하기 때문이다.

따라서 너비가 N, 높이가 logN이라고 생각하면 시간 복잡도는 O(N * log_2(N)) 이다.

 

평균, 최악, 최고 모두  O(N * log_2(N)) 이다.

왜냐하면 머지소트는 항상 배열을 둘로 나누고 선형 시간만큼 그 둘을 합치기 때문이다.

 

이번엔 수식으로 증명해보자.

재귀 알고리즘이라는 점에 주목하자. 

T(n) = 2T(n/2) + ɵ(n)

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

위는 합병 정렬의 슈도 코드이다.

 

1. 가운데를 찾아 두 배열로 나눈다. middle m = (l+r)/2

2. 앞 절반에 대하여 mergeSort 함수를 호출한다. Call mergeSort(arr, l, m)

3. 뒤 절반에 대하여 mergeSort 함수를 호출한다. Call mergeSort(arr, m+1, r)

4. 2와 3에서 정렬된 두개의 반으로 나눠진 리스트들을 합친다. : Call merge(arr, l, m, r)

 

두 가지 방식으로 재귀식의 시간복잡도를 증명할 수 있다.