합병 정렬은 분할 정복 방법을 사용한다.
합병 정렬을 공부하기 전에, 동적 계획법과 분할 정복에 대해 먼저 알아보겠다.

동적 계획법(Dynamic Programming)

• 작은 문제를 해결한 후, 해당 부분의 해를 활용해 더 큰 크기의 문제를 해결한다.
• 상향식 접근법 : 가장 최하위 답을 구한 후, 결과값을 이용해 상위 문제를 풀어가는 방식
• Memoization 기법을 사용함 : 프로그램 실행 시 이전에 계산한 값을 저장해, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• ex) 문제를 잘게 쪼갤 때 사용됨, 부분 문제는 중복되어 재활용됨 - 피보나치 수열

분할과 정복(Divide and Conquer)

• 문제를 나눌 수 없을 때까지 나누어 각각을 풀고 다시 합병해 답을 얻는 알고리즘이다.
• 하향식 접근법 : 상위의 해답을 구하기 위해, 아래로 내려가면서 해답을 구하는 방식
• ex) 문제를 잘게 쪼갤 때 사용됨, 부분 문제는 중복되지 않음 - 병합 정렬, 퀵 정렬!

합병 정렬(Merge Sort)

분할 정복 방법으로 숫자를 정렬하는 알고리즘
데이터를 잘게(길이가 1이 되도록) 쪼개 두개씩 크기를 비교해 정렬하는 알고리즘

구현

github link

1. merge_sort( ) 함수

def merge_sort(list):
    if (len(list) <= 1):
        return list
    mid = len(list) // 2
    left_list = list[:mid]
    right_list = list[mid:]
    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return merge(left_list, right_list)

분할과 정복 방법을 사용해 리스트 길이가 1이 될 때까지 나눈다.

2. merge( ) 함수

def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) >0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]

        # 왼쪽 리스트만 남는 경우
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]

        # 오른쪽 리스트만 남는 경우
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result

merge_sort()를 이용해 분리한 리스트를 다시 합친다.
① left_list와 right_list의 첫번째 요소를 비교해 작은 값을 결과 리스트(result)에 저장
② result에 저장한 값을 left_list, right_list에서 삭제
③ left_list와 right_list에 남는 요소가 없을 때까지 반복

References
나동빈 알고리즘 강의