[Python] 병합 정렬 (Merge Sort)

병합정렬도 대표적인 '분할 정복' 방법을 채택한 알고리즘

퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가진다. 퀵정렬은 피벗값에 따라 최악의 경우 O(N^2)의 시간 복잡도를 가질 수 있는데 병합정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장한다.

 

 

 

 

일단 반으로 나누고 나중에 합쳐서 정렬하자

병합정렬은 항상 반으로 나누기 때문에 피벗값이 따로 없다. 반으로 쪼개기 때문에 항상 logN을 보장한다. 합칠때는 2의 배수만큼 합친다. 

 

 

 

 

# 병합 정렬 (Merge sort)
# 정렬배열은 반드시 전역 변수로 선언해줘야한다. (추가적인 배열)
sortedArr = []

def merge(arr, start, middle, end): # start : m , end : n
    i = start
    j = middle + 1
    k = start
    
    # 작은 순서대로 배열에 삽입
    # i는 middle까지 가고 j는 end까지 간다.
    while i <= middle and j <= end:
        # 항상 i랑 j를 비교해서 더 작은 값을 k에 넣는다.
        if arr[i] <= arr[j]:
            sortedArr[k] = arr[i]
            i = i + 1
        else:
            sortedArr[k] = arr[j]
            j = j + 1
        k = k + 1
    
        # 남은 데이터도 삽입
        if i > middle : # i 가 먼저 끝난 경우
            for t in range(j, end + 1):
                sortedArr[k] = arr[t]
                k = k + 1
        else: # j가 먼저 끝난경우
            for t in range(i, middle + 1):
                sortedArr[k] = arr[t]
                k = k + 1
        
        
        # 정렬된 배열을 삽입
        for t in range(start, end+1):
            arr[t] = sortedArr[t]
            

def merge_sort(arr, start, end):
    # 크기가 1보다 큰 경우
    if start < end :
        middle = (start + end) / 2
        merge_sort(arr, start, middle)
        merge_sort(arr, middle + 1, end)
        merge(arr, start, middle, end)
    
    return arr
        
        

test = [7,6,5,8,3,5,9,1]

print("정렬된 배열 : {}".format(merge_sort(test, 0, len(test)-1)))

이 코드 실행안됨;