[파이썬 자료구조] 합병정렬

리스트 분리해서 합칠때 정렬하는 방법입니다! 각각 재귀적으로 정렬을 수행하고 두개의 정렬된 배열을 합칩니다.

각각의 리스트의 맨 앞의 값을 비교해서 둘 중 작은 값을 새로운 리스트의 맨 앞에 삽입합니다.

파이썬으로 구현해보면 

def merge_sort(L):
    n = len(L)
    if n < 2:
        return 
    mid = n // 2
    L1 = L[:mid] 
    L2 = L[mid:] 
    merge_sort(L1) 
    merge_sort(L2) 
    merge(L1, L2, L) 
 
def merge(S1, S2, S):
    i = j = 0
    while i + j < len(S):
        if j == len(S2) or (I < len(S1) and S1[i] < S2[j]):
            S[i + j] = S1[i]
            i += 1
        else:
            S[i + j] = S2[j]
            j += 1

합병정렬은 나누는 과정과 합치는 과정으로 수행합니다.

merge_sort에서 자기 자신을 두개의 리스트로 재귀적으로 나눕니다. 리스트의 길이가 2개보다 작다면 return문을 수행

나눠진 리스트들을 merge함수를 통해 합쳐줍니다.

merge함수에서 S1,S2를 합쳐서 S리스트를 만듭니다. 15번째 줄에서 S1과 S2의 맨 앞의 값을 비교해서 둘중 작은 값을 S리스트의 맨 앞에 삽입해 줍니다.

그러면 시간 복잡도를 알아보겠습니다.

n개의 원소를 합병정렬하는 시간을 T(n)으로 하면 이 리스트를 두개로나누기 때문에 2T(n/2) + cn이 됩니다.

cn은 합치는데 걸리는 시간입니다. 합치는데 걸리는 시간은 O(n)임을 알 수 있습니다.(n번 비교하기때문)