Ch.8 정렬과 탐색

Merge Sort — 분할 정복의 정석

Merge Sort의 분할-병합 과정을 단계별로 설명한다O(n log n) 시간 복잡도가 왜 나오는지 유도한다

반으로 나누고, 합치면서 정렬한다

52장의 카드를 혼자 정렬하기 어렵지만, 26장씩 나눠 두 사람이 각각 정렬한 뒤 합치면 훨씬 빠릅니다.

나누는 데도 시간이 드는데, 어떻게 전체적으로 더 빨라질 수 있을까?

분할의 깊이는 log n, 각 층에서 n번 비교 — 합하면 O(n log n)입니다.

lightbulb

핵심 개념

분할 정복

문제를 작은 부분으로 나누어 해결하고 합치는 전략

Merge Sort

배열을 반으로 나누고 정렬된 부분을 병합하는 O(n log n) 정렬

article

핵심 내용

큰 문제를 반으로 나누고 작은 문제부터 해결합니다

배열 [5, 3, 8, 1]을 예시로 Merge Sort 과정을 봅시다

1. 분할: [5,3,8,1] → [5,3] + [8,1] 2. 분할: [5,3] → [5]+[3], [8,1] → [8]+[1] 3. 병합: [5]+[3] → [3,5], [8]+[1] → [1,8] 4. 병합: [3,5]+[1,8] → [1,3,5,8]

핵심은 merge 함수입니다. 두 정렬된 배열을 합치는 로직

def merge_sort(arr):
    if len(arr) <= 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):
    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

`left[i] <= right[j]`에서 <= 가 안정 정렬의 비결입니다 — 같은 값이면 왼쪽(원래 앞)을 먼저 넣음

merge([3, 5], [1, 8])이 어떻게 동작하는지 추적합니다

두 포인터가 각각 한 번씩만 이동하므로 merge는 O(n) 입니다

왜 O(n log n)인지 직관적으로 이해해봅시다

분할 깊이: n을 반으로 나누는 횟수 = log₂ n 각 층의 비교: 모든 원소가 한 번씩 비교 = n → 전체: n × log n = O(n log n)

공간 복잡도: O(n) merge 시 임시 배열이 필요합니다. 이것이 Merge Sort의 유일한 단점입니다.

Merge Sort는 항상 O(n log n) — 최선/평균/최악 모두 동일합니다

Merge Sort의 면접 출제 포인트를 정리합니다

면접 빈출 질문: 1. Merge Sort vs Quick Sort 차이? 2. 왜 Merge Sort는 안정 정렬인가? 3. 공간 복잡도가 O(n)인 이유? 4. Linked List 정렬 시 왜 Merge Sort가 유리한가?

Linked List 정렬 = Merge Sort가 최적! random access 불필요 + 추가 공간 O(1)

Merge Sort의 공간 복잡도는?

Merge Sort의 최악 시간 복잡도는 O(n²)이다

분할 정복 마스터!

key

핵심 용어

✂️

Divide

배열을 반으로 나눈다

🔄

Conquer

각 반쪽을 재귀적으로 정렬한다

🔗

Merge

정렬된 두 배열을 합친다

edit_note

정리 노트

Merge Sort — 분할 정복

핵심 개념

전략: 분할 → 재귀 정렬 → 병합
시간: 항상 O(n log n) (최선=평균=최악)
공간: O(n) — 임시 배열 필요

면접 포인트

안정 정렬: `<=` 비교로 같은 값 순서 유지
Linked List: Merge Sort가 최적 — random access 불필요

★

Merge Sort는 '안정성이 필요할 때'와 'Linked List 정렬'에서 꺼내는 카드!

image

시각 자료

다이어그램: ds-d62

check_circle

핵심 정리

1Merge Sort = Divide + Conquer + Merge
2항상 O(n log n), 공간 O(n)
3안정 정렬, Linked List에 최적

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작