병합 정렬이란?
병합 정렬(Merge Sort)은 배열을 반으로 계속 쪼개 더 이상 나눌 수 없을 때까지 내려간 뒤, 정렬된 두 조각을 합치며(merge) 올라오는 분할 정복 알고리즘입니다. "나누기"는 쉽고, 진짜 일은 "합치기"에서 일어납니다.
핵심 한 줄: "이미 정렬된 두 배열을 합치는 것은 빠르다." 두 조각이 각각 정렬돼 있으면, 앞에서부터 더 작은 것을 하나씩 골라 담는 것만으로 O(n)에 합쳐집니다.
핵심은 병합(merge)
정렬된 두 배열 A, B를 합친다고 합시다.
1. A와 B의 맨 앞을 가리키는 포인터를 둡니다.
2. 두 포인터가 가리키는 값 중 더 작은 값을 결과에 담고, 그 포인터만 한 칸 옮깁니다.
3. 한쪽이 비면 남은 쪽을 그대로 이어 붙입니다.
각 원소를 정확히 한 번씩만 보므로 병합은 O(n)입니다. 이 병합을 깊이 log n만큼 반복하니 전체가 O(n log n)입니다.
동작 원리
1단계. 구간 [lo, hi]의 가운데 mid를 기준으로 왼쪽 [lo, mid]와 오른쪽 [mid+1, hi]로 나눕니다.
2단계. 왼쪽과 오른쪽을 각각 재귀로 정렬합니다. 구간 크기가 1이면 이미 정렬된 것으로 보고 멈춥니다(기저 사례).
3단계. 정렬된 두 구간을 위의 병합 절차로 하나의 정렬된 구간으로 합칩니다.
4단계. 재귀가 위로 올라오며 점점 큰 구간이 합쳐지고, 마지막에 전체가 정렬됩니다.
"나누는" 동작과 "합치는" 동작은 별개입니다. 알고노트 시각화도 분할 단계와 병합 단계를 구분해 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n log n) |
| 공간 | O(n) |
분할 깊이가 항상 log n이고 각 깊이의 병합이 O(n)이라, 입력이 어떻든 항상 O(n log n)을 보장합니다(퀵 정렬과 달리 최악 케이스가 없음). 대신 병합용 임시 배열이 필요해 공간은 O(n)입니다.
예시로 따라가기
[5, 2, 8, 1]을 정렬해 봅시다.
- •나누기:
[5, 2]와[8, 1] - •각각 정렬:
[2, 5]와[1, 8] - •병합: 2 vs 1 → 1, 2 vs 8 → 2, 5 vs 8 → 5, 남은 8 →
[1, 2, 5, 8]
작은 조각이 정렬된 채로 합쳐지며 전체가 완성됩니다.
자주 하는 실수
- •임시 배열: 병합 결과를 임시 배열에 담은 뒤 원본에 복사하는 단계를 빠뜨리면 값이 덮어써집니다.
- •안정성 유지: 두 값이 같을 때 왼쪽(앞 구간) 값을 먼저 담아야 안정 정렬이 됩니다(같은 값의 원래 순서 보존).
- •mid 계산:
(lo + hi) / 2는 큰 수에서 오버플로 위험 →lo + (hi - lo) / 2가 안전합니다.
알고노트에서 직접 확인하세요
배열이 어떻게 반으로 쪼개지고, 정렬된 두 조각이 더 작은 값부터 차례로 합쳐지는지 알고노트에서 단계별로 확인할 수 있습니다.