병합 정렬: 나누고, 정복하고, 합치고

"병합 정렬 아이디어 전체가 한 문장에 들어가: 쉽게 못 푸는 문제를, 반으로 쪼개고, 각 반을 풀고, 답을 꿰매 합쳐. 그 '쪼개고, 풀고, 합치고' 리듬이 분할 정복이고, 정렬을 훨씬 넘어가."

세 단계

병합 정렬은 분할 정복의 가장 깔끔한 예야:

나누기: 배열을 두 반으로 쪼개.
정복: 각 반을 재귀적으로 정렬 (재귀가 단일 원소에서 바닥 치고, 그건 자명하게 정렬됨).
합치기: 정렬된 두 반을 하나의 정렬 전체로 병합.

영리한 부분은 병합이야: 이미 정렬된 두 반이 주어지면, 각각에 포인터를 내리며, 두 앞쪽 중 더 작은 걸 반복해 가져와. 두 반이 정렬돼서, 이게 단일 O(n) 패스에 완전 정렬 결과를 만들어 — Arrays 트랙의 투 포인터 기법이, 진짜 일을 해.

왜 보장된 O(n log n) 인가

레벨로 일을 세. 반복 절반 내기가 log n 레벨 재귀를 줘 (n → n/2 → n/4 → … → 1). 각 레벨에서, 모든 조각의 병합이 함께 모든 n 원소를 한 번 건드려 — 레벨당 O(n). 그래서 총 일이 n × log n = O(n log n). 그리고 결정적으로, 이게 입력과 무관하게 성립해 — 퀵소트와 달리, 병합 정렬은 나쁜-피벗 최악 케이스가 없어; 정렬 데이터, 역순 데이터, 무작위 데이터에 늘 O(n log n). 그 보장이 그 명함이야.

병합 정렬: 반 나누고, 각 반 재귀 정렬, 두 포인터로 O(n) 에 정렬된 반을 병합. log n 레벨 × 레벨당 O(n) = 모든 입력에 보장된 O(n log n). 안정적이지만 병합에 O(n) 추가 공간을 써.

강점과 비용

병합 정렬은 두드러진 미덕 둘이 있어. 안정적 — 같은 원소가 원래 상대 순서를 지켜, 한 키로 정렬 후 또 다른 키로 정렬할 때 중요해 (이름으로 정렬, 그다음 날짜로 안정 정렬하면, 같은-날짜 항목이 이름-순서 유지). 그리고 아름답게 병렬화/외부화돼: 외부 정렬 (메모리에 비해 너무 큰 데이터를, 디스크의 정렬된 청크를 병합해 정렬) 의 기반이고 연결 리스트 를 잘 정렬해 (퀵소트와 달리 임의 접근 불필요). 비용은 병합 버퍼용 O(n) 추가 공간 — 그게 다음 lesson 이 다루는 퀵소트의 제자리 분할 대비 거래야.

피파의 고백

병합 단계가 날 헷갈리게 했는데 아빠가 정렬된 두 줄의 사람이 하나로 합쳐지는 걸로 짰어: 두 줄 앞에서 더 짧은 사람을 계속 가져오면 돼. 보고 나면 당연해. 근데 나한테 남은 건 정렬보다 컸어 — '쪼개고, 조각을 풀고, 합치고' 가 그냥 정렬이 아니라 전략이었어. 다음 트랙 (재귀) 이 사실 그 분할 정복 모양을 어디서나 보는 법을 배우는 거고, 병합 정렬이 나한테 그게 처음 딸깍한 데야.

Code

병합 정렬: 쪼개고, 재귀, 병합·python

def merge_sort(arr):
    if len(arr) <= 1:                 # base case: 0 또는 1 원소는 정렬됨
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # 나누기 + 정복: 각 반 정렬
    right = merge_sort(arr[mid:])
    return merge(left, right)         # 합치기

def merge(left, right):
    """정렬된 두 리스트를 하나로 병합, O(n), 두 포인터로."""
    result, i, j = [], 0, 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:])           # 남은 거 append
    result.extend(right[j:])
    return result

print(merge_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]
# log n 레벨 절반 내기, 레벨당 O(n) 병합 -> O(n log n), 모든 입력.
# 두 포인터 병합이 엔진; 재귀는 그냥 그걸 차려.

Exercise

[3, 1, 2] 에 병합 정렬을 추적해: 단일 원소까지 재귀 쪼개기를 보이고, 그다음 다시 위로 병합. 따로, 병합 정렬은 왜 *모든* 입력에 O(n log n) 인데 퀵소트는 O(n²) 로 떨어질 수 있는지 설명해 — 병합 정렬 구조의 뭐가 나쁜 케이스를 막아?

Hint

[3,1,2] → [3] 이랑 [1,2] → [1],[2] 가 [1,2] 로 병합; 그다음 [3] 이랑 [1,2] 병합 → [1,2,3]. 병합 정렬은 값과 무관하게 늘 정확히 반 쪼개, 그래서 늘 log n 레벨 — 잘못될 피벗 선택이 없어, 그래서 O(n²) 최악 케이스 없음.

세 단계

왜 보장된 O(n log n) 인가

강점과 비용

피파의 고백

Code

External links

Exercise

Progress

댓글 0