[python](알고리즘) mergeSort 병합정렬(합병정렬) 구현

Merge sort(합병정렬) 구현

코드

def merge_sort(list):
    if len(list) <= 1:  # base case: 리스트에 원소가 하나 밖에 없을 때
        return list

    mid = len(list) // 2  # 리스트의 중간지점
    left_list = list[:mid]  # 리스트의 왼쪽 부분
    right_list = list[mid:]  # 리스트의 오른쪽 부분

    left_list = merge_sort(left_list)  # 재귀함수를 호출하여 다시 나눈다.
    right_list = merge_sort(right_list)

    return merge(left_list, right_list)  # 왼쪽부터 오른쪽으로 merge

def merge(left, right):
    i = 0
    j = 0
    merge_list = []

    while i < len(left) and j < len(right):  # left, right 가 아직 남아있을 때
        if right[j] < left[i]:
            merge_list.append(right[j])
            j += 1
        else:
            merge_list.append(left[i])
            i += 1

    if (i < len(left)): #left 만 남아있을 때, 리스트에 리스트를 합친다.
        merge_list += left[i:len(left)]
    else:
        merge_list += right[j:len(right)]

    return merge_list

data_list = [-1, 10, 20, 7, 15, 30, 40, 50, 32, 5]
print(merge_sort(data_list))

실행결과

[-1, 5, 7, 10, 15, 20, 30, 32, 40, 50]

시간복잡도

O(nlogn)