합병 정렬

합병 정렬(merge sort)

시간 복잡도는 $\theta{(n \times logn)}$

파이썬 소스코드

def merge(arr, l, m, r):
    i = 0
    j = 0
    k = l
    left_sub = arr[l:m+1]
    right_sub = arr[m+1:r+1]

    while i <= m-l and j <= r-m-1: # the length of left and right sub array
        if left_sub[i] <= right_sub[j]:
            arr[k] = left_sub[i]
            i += 1
        elif left_sub[i] > right_sub[j]:
            arr[k] = right_sub[j]
            j += 1
        k += 1
    
    while i <= m-l:
        arr[k] = left_sub[i]
        i += 1
        k += 1
    
    while j <= r-m-1:
        arr[k] = right_sub[j]
        j += 1
        k += 1


def merge_sort(arr, l, r):
    m = (l+r) // 2
    if l < r:
        merge_sort(arr, l, m)
        merge_sort(arr, m+1, r)
        merge(arr, l, m, r)


a = [11, 10, 3, 7, 9, 15, 13, 23, 22]
print("Before sorting {}".format(a))
merge_sort(a, 0, len(a)-1)
print("After sorting {}".format(a))

 

Before sorting [11, 10, 3, 7, 9, 15, 13, 23, 22]
After sorting [3, 7, 9, 10, 11, 13, 15, 22, 23]