[파이썬] 합병 정렬

합병 정렬은 두 리스트를 리스트가 하나가 남을 때까지 Divide하여

리스트가 1개인 것들끼리 비교하여 Conquer하고

서로 정렬된 리스트에 합쳐 combine하는 식으로 구성한다.

 

완성된 코드는 이러하며

def merge(list1, list2):
    merged_list = []
    i = 0
    j = 0

    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

    merged_list = merged_list + list1[i:] + list2[j:]
    return merged_list


def merge_sort(my_list):
    # base case
    if len(my_list) < 2:
        return my_list
    # recursive case
    else:
        left_half = []
        right_half = []
        for i in range((len(my_list) // 2)):
            left_half.append(my_list[i])
        for j in range((len(my_list) // 2), len(my_list)):
            right_half.append(my_list[j])
        return merge(merge_sort(left_half), merge_sort(right_half))

 

복잡도를 이런식으로 최소화 할 수 있을 것 같다.

 

def merge(list1, list2):
    merged_list = []
    i = 0
    j = 0

    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

    merged_list = merged_list + list1[i:] + list2[j:]
    return merged_list


def merge_sort(my_list):
    # base case
    if len(my_list) < 2:
        return my_list
    # recursive case
    else:
        left_half = my_list[:len(my_list) // 2]  # 왼쪽 반
        right_half = my_list[len(my_list) // 2:]  # 오른쪽 반

        return merge(merge_sort(left_half), merge_sort(right_half))