합병 정렬 with. Divide and Conquer

풀이법

Divide : 리스트를 반으로 나눈다.

Conquer : 왼쪽과 오른쪽 각각 정렬을 수행

Combine : 정렬된 두 리스트를 하나의 정렬된 리스트로 합병

 - 왼쪽과 오른쪽의 맨 앞의 원소가 제일 작으므로 맨 앞의 원소부터 비교를 해서 작은것부터 넣어줘야함

 

def merge(list1, list2):
    return sorted(list1 + list2)

# 합병 정렬
def merge_sort(my_list):
    if len(my_list) < 2:
        return my_list
    mid = len(my_list) // 2
    
    return merge(merge_sort(my_list[0:mid]), merge_sort(my_list[mid:]))

# 테스트 코드
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))