4 / 16강

나누고 합치는 분할 정복

큰 목록을 한 번에 정리하기 어렵다면 두 묶음으로 나눕니다. 각 묶음을 정렬한 뒤 맨 앞의 작은 값부터 꺼내 합칩니다. 분할 정복은 나누기, 풀기, 합치기의 순서로 문제를 해결합니다.

합병 정렬의 흐름

[8, 3, 6, 1]을 [8, 3]과 [6, 1]로 나눕니다. 다시 하나씩 나누면 이미 정렬된 상태입니다. [3, 8]과 [1, 6]으로 합친 뒤, 1 → 3 → 6 → 8 순서로 최종 목록을 만듭니다.

def merge_sort(values):
    if len(values) <= 1:
        return values.copy()
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([8, 3, 6, 1]))

결과는 [1, 3, 6, 8]입니다. len(values) <= 1은 나누기를 멈추는 조건입니다. <=로 왼쪽을 먼저 고르므로 같은 값의 원래 순서도 유지합니다.

절반씩 나눴는데 왜 O(log n)이 아닐까요?

나누는 깊이는 약 log₂ n입니다. 하지만 각 깊이에서 모든 원소를 합치는 일이 총 O(n)만큼 필요합니다. 따라서 전체는 O(n log n)입니다. 두 부분을 모두 푼다는 것을 식으로 적으면 T(n) = 2T(n/2) + O(n)입니다.

이진 탐색은 한쪽만 계속 찾으므로 T(n) = T(n/2) + O(1)이고 O(log n)입니다. 절반으로 나눈다는 사실만 같을 뿐, 이어서 처리하는 양이 다릅니다.

위 합병 정렬은 새 목록을 만드는 데 최대 O(n)의 추가 공간을 씁니다. 퀵 정렬은 피벗을 기준으로 먼저 나누며, 분할이 균형적인지에 따라 비용이 달라집니다.

확인 문제

합치는 단계에서 더 큰 값을 먼저 꺼내면 여전히 오름차순으로 정렬될까요? 나누기만 제대로 하면 충분할까요?