~11 min · searching-sorting, merge-sort, divide-conquer
Level 0호기심 많은 입문자
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"병합 정렬의 아이디어는 한 문장에 다 들어가. 한 번에 못 푸는 문제를 반으로 쪼개고, 각 반을 풀고, 답을 꿰매 붙이는 거야. 이 '쪼개고, 풀고, 합치고'라는 리듬이 분할 정복이고, 정렬을 훨씬 넘어서 쓰여."
세 단계
병합 정렬은 분할 정복의 가장 깔끔한 예야.
나누기. 배열을 두 반으로 쪼개.
정복. 각 반을 재귀적으로 정렬해. 재귀는 원소 하나에서 바닥을 치는데, 원소 하나짜리는 이미 정렬된 거니까.
합치기. 정렬된 두 반을 하나의 정렬된 전체로 병합해.
영리한 대목은 병합이야. 이미 정렬된 두 반이 있으면 각각에 포인터를 하나씩 두고 내려가면서 두 앞머리 중 더 작은 걸 계속 가져오면 돼. 양쪽이 정렬돼 있으니까 이 한 번의 O(n) 훑기로 완전히 정렬된 결과가 나와. 배열과 문자열 트랙에서 배운 투 포인터 기법이 여기서 진짜 일을 하는 거야.
왜 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) 추가 공간이고, 그게 다음에 볼 퀵소트의 제자리 분할과 맞바꾸는 조건이야.
피파의 고백
병합 단계가 잘 안 잡혔는데 아빠가 이렇게 설명해 줬어. 줄을 선 사람 두 무리가 하나로 합쳐지는 장면인데, 두 줄의 맨 앞에서 키가 더 작은 사람을 계속 데려오면 된다고. 듣고 나니 당연했지. 그런데 나한테 남은 건 정렬보다 큰 거였어. '쪼개고, 조각을 풀고, 합친다'가 정렬 기법이 아니라 전략이었던 거야. 다음 트랙인 재귀는 사실 그 분할 정복 모양을 여기저기서 알아보는 법을 배우는 거고, 나한테 그게 처음 맞아떨어진 자리가 병합 정렬이었어.
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), 모든 입력.
# 두 포인터 병합이 엔진. 재귀는 그냥 그걸 차려.
[3, 1, 2]에 병합 정렬을 따라가 봐. 원소 하나가 될 때까지 재귀적으로 쪼개는 과정을 보이고, 그다음 다시 위로 병합해. 따로, 병합 정렬은 왜 어떤 입력에서든 O(n log n)인데 퀵소트는 O(n²)로 떨어질 수 있는지도 설명해. 병합 정렬 구조의 어떤 점이 나쁜 경우를 막아 줄까?
Hint
[3,1,2]는 [3]과 [1,2]로 갈리고, [1,2]는 다시 [1]과 [2]로 갈렸다가 [1,2]로 합쳐져. 그다음 [3]과 [1,2]를 병합하면 [1,2,3]이야. 병합 정렬은 값이 뭐든 상관없이 언제나 정확히 반으로 쪼개니까 항상 log n 단계가 나와. 잘못 고를 피벗이라는 게 아예 없으니 O(n²) 최악의 경우도 없는 거고.
Progress
Progress is local-only — sign in to sync across devices.