병합 정렬

def merge_sort(arr) :
    n = len(arr)

    # basis case
    if n <= 1 :
        return arr

    mid = n//2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right) :
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right) :
        if left[i] < right[j] :
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

print(merge_sort([9,3,55,5,5,7,1,1,2,10,22]))

 

 

병합 메서드 이렇게도 구현 가능

def merge(left, right) :
    result = []

    while left and right :
        if left[0] < right[0] :
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    result.extend(left)
    result.extend(right)

    return result