[Divide and Conquer] Merge Sort 구현하기 - Python

코드잇 강의를 통해 알고리즘에 대해 공부하며 배운 내용들을 기록한 글입니다.

---

문제 설명

Divide and Conquer 방식으로 merge_sort 함수를 만들어라!
merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴한다.

merge 함수는 이전 과제에서 작성한 그대로 사용하면 된다!

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

    merged_list = []

    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

    if i == len(list1):
        merged_list += list2[j:]

    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list


def merge_sort(my_list):
   

# 테스트 코드
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]))

---

나의 풀이

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

    merged_list = []

    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

    if i == len(list1):
        merged_list += list2[j:]

    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list


def merge_sort(my_list):
    if len(my_list) < 2:
        return my_list

    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))

# 테스트 코드
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]))

merge_sort의 base case는 리스트의 길이가 $0$이나 $1$일 경우이다.
왜냐하면, 무조건 정렬된 리스트이기 때문이다.
그 경우에는 리스트를 바로 리턴해주면 된다.

def merge_sort(my_list):
    if len(my_list) < 2:
        return my_list
             

base case가 아닌 경우에는 리스트를 반으로 나누어야 한다.
그러기 위해서 나는 리스트의 왼쪽 반을 left_half라는 변수에, 오른쪽 반을 right_half라는 변수에 넣기로 했다.

merge_sort(left_half)를 하면 재귀 함수를 통해 정렬된 left_half가 리턴되고, merge_sort(right_half)를 하면 정렬된 right_half가 리턴된다.

이제 정렬된 두 리스트를 merge함수의 파라미터로 넘겨주면 combine이 진행되고, my_list의 정렬이 끝이 난다!