정렬 알고리즘 두번째 시간입니다 :-) 이번엔 Merge Sort에 대해 살펴볼 건데요, 앞서 살펴봤었던 bubble sort($O(N^2)$)에 비해 average case performance가 $O(N\log N)$으로 엄청나게 향상되는 알고리즘입니다. 결국 이 merge sort도 메모리를 많이 사용하기 때문에 다른 알고리즘이 결국 많이 사용되지만, 그래도 알고리즘에서 접근법으로 가장 많이 쓰는 Divide and Conquer 방식이 도입되는 문제이기 때문에 확실히 익히시고 넘어가셔야 합니다.

먼저 동작 방식에 대해서 위키에 있는 그림으로 살펴보겠습니다.

merge sort

위의 그림과 같이, merge sort는 주어진 집합 A를 recursively 반씩 쪼개서 하나의 원소만 갖는 list에서 역으로 함수를 끝내갈 때에 순서대로 정렬해 올라가는 방식입니다. 이것이 바로 Divide and Conquer의 전형적인 예인데요, 이것을 수식으로 표현해 보면, \[T(n)=2T\left(\frac{n}{2}\right)+n\] 이는 결국 전개하면, \[\begin{aligned} T(n)&=2\left(2T\left(\frac{n}{4}\right)+\frac{n}{2}\right)+n \newline &=4T\left(\frac{n}{4}\right)+n+n\newline &=…\newline &\approx O(\underbrace{n+n+…+n}_{\log n})\newline &=O(n\log n) \end{aligned}\] 이 됨을 확인할 수 있죠 :) 이제 이것을 어떻게 코드로 짤지 생각해 봐야겠습니다. 보통 Divide and Conquer문제들은 recursive 함수로 구현합니다. 앞의 수식에서 조금은 직관적으로 눈치채셨나요? Base case는 주어진 list가 1개의 원소나 또는 비어있는 list일 경우일 것입니다. Return되는 list는 모두 정렬된 상태로 돌려줘야 합니다.

def mergeSort(A):
	### Base case ###
    if len(A) <= 1:
        return A

    ### A를 반으로 쪼개서 recursive call을 해 주고 정렬된 반쪽짜리들을 받아옵니다.   
    left = mergeSort(A[:len(A)/2])
    right = mergeSort(A[len(A)/2:])

    ### 여기서부터 두 개의 쪼개졌던 list를 합치는 Merge 부분입니다.
    ### 여기서 포인트는 정렬된 상태로 돌아왔기 때문에 앞에서부터 순차적으로 한번만 돌면 정렬시킬 수 있다는 것입니다.
    i, j, k = 0, 0, 0
    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            A[k] = left[i]
            i += 1
        else:
            A[k] = right[j]
            j += 1
        k += 1
    if i == len(left): #만약 left의 원소를 모두 채웠고, right가 남아있을 때.
        while j<len(right):
            A[k] = right[j]
            j += 1
            k += 1
    elif j == len(right): #만약 right의 원소를 모두 채웠고, left가 남아있을 때.
        while i<len(left):
            A[k] = left[i]
            i += 1
            k += 1
    return A #마지막으로 정렬된 list를 리턴합니다.

제법 코드는 길지만, 실제로 동작 시간은 그리 길지 않아요~ 비교 구문 자체는 굉장히 실행시간이 짧거든요. 이제 잘 동작하는지 확인해 봅시다.

>>> import random
>>> A=[random.randint(1,100) for _ in range(10)]
>>> mergeSort(A)
[29, 42, 43, 49, 59, 61, 63, 80, 80, 97]

랜덤하게 발생시킨 경우니까 여러분들이 다시 실행할 때는 다른 숫자들이 등장할 수 있어요. 하지만 결국 오름차순으로 정렬되는 것은 똑같답니다 :) 꼭 스스로 한번씩 짜 보시면 좋을 것 같네요.