4. 합병 정렬과 분할 정복법 (Merge Sort, Devide and Conquer)

분할 정복법^{Devide and Conquer}

분할 정복법은 대표적인 알고리즘 설계 기법의 일종으로, 큰 문제를 작은 문제 여러 개로 분할하여, 하나씩 해결하는 기법이다.

분할 정복의 예시로 합병 정렬과 퀵 정렬이 있다.

합병 정렬

분할 정복법을 이용한 정렬 알고리즘이다. 힙 정렬과 마찬가지로 비교에 기초한 정렬이며, $O(n\log n)$ 시간에 수행된다.

힙 정렬과는 달리 외부의 우선순위 큐를 이용하는 것이 아니라, 데이터에 순차적으로 접근하여 정렬하므로, 순차 데이터를 정렬하기에 적절하다.

def mergeSort(L):
    if len(L) > 1:
    	L1, L2 = L[:len(L)//2], L[len(L)//2:] # Devide
        mergeSort(L1) # Conquer
        mergeSort(L2)
        L = merge(L1, L2) # Solved
    return L
def merge(L1, L2):
    L = []
    while not L1.isEmpty() and not L2.isEmpty():
        if L1[1] <= L2[1]:
            L.append(L1.removeFirst())
        else
            L.append(L2.removeFirst())
    while not L1.isEmpty():
        L.append(L1.removeFirst())
    while not L2.isEmpty():
        L.append(L2.removeFirst())
    return L

L1, L2 리스트는 각각 $n/2$개의 원소를 가지며, 이중연결리스트로 구현된 두 리스트를 합병하는데 $O(n)$ 시간이 소요된다.

merge 함수가 $\log n$회 수행되므로, 시간 복잡도는 $O(n\log n$이다.