합병 정렬

: 두 정렬된 리스트를 하나의 정렬된 리스트로 합병하는 방법

1. Divide: 리스트를 반으로 나눈다.
2. Conquer: 왼쪽 리스트와 오른쪽 리스트를 각각 정렬한다.
3. Combine: 정렬된 두 리스트를 하나의 정렬된 리스트로 합병한다.

진행 과정

예시) 16 11 6 13 1 7 10 4

• 16 11 6 13 1 7 10 4

  → 리스트가 길기 때문에 재귀적으로 또 Divide & Conquer를 해준다.

• 16 11 6 13

  → 리스트가 충분히 작지 않으므로 재귀적으로 또 Divide & Conquer를 해준다.

• 16 11

  → 리스트의 요소가 하나밖에 없기 때문에 이미 정복했다고 할 수 있다.

  → 정복한 두 부분 문제의 솔루션을 갖고 Combine 단계에서 합쳐준다.

• 11 16 → 정복 완 !

• 6 13

• 6 13 → 정복 완 !

• 두 정렬된 리스트를 합쳐준다. (11 16 6 13)

  • 가장 왼쪽 값들만 보면 된다. → 6 11 13 16

• 1 7 10 4

• 1 7

• 1 7

• 10 4

• 4 10

• 1 7 4 10 → 1 4 7 10

• 1 4 6 7 10 11 13 16

merge 함수

: 정렬된 두 리스트 list1과 list2를 파라미터로 받고, 합쳐진 리스트를 리턴해준다.

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

    merged_list = []

    # list1과 list2를 돌면서 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

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list

합병 정렬 구현

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

    # 정렬된 항목들을 담을 리스트
    merged_list = []

    # list1과 list2를 돌면서 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

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list

def merge_sort(my_list):
    # base case
    if len(my_list) < 2:
        return my_list

    # my_list를 반씩 나눈다(divide)
    left_half = my_list[:len(my_list)//2]    # 왼쪽 반
    right_half = my_list[len(my_list)//2:]   # 오른쪽 반

    # merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
    # merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
    return merge(merge_sort(left_half), merge_sort(right_half))

• 시간 복잡도: O(nlogn)