3) 합병 함수를 Divide and Conquer 방식으로 작성

3. 합병 함수를 Divide and Conquer 방식으로 작성

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(list1[i])
            i += 1
        else:
            merged_list.append(list2[j])
            j += 1
    merged_list = merged_list + list1[i:] + list2[j:]

    return merged_list
    
# 합병 정렬
def merge_sort(my_list):
    if len(my_list)==1:
        return my_list
    mid = len(my_list)//2
    return merge(merge_sort(my_list[: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]))

# 결과
# [1, 3, 5, 7, 9, 11, 11, 13]
# [1, 5, 7, 9, 13, 15, 28, 30, 48]
# [1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]