배열을 반으로 나눠 정렬한 뒤 다시 합치는 병합 정렬을 막대 애니메이션으로 확인하세요. O(n log n)이 보장되는 이유와 임시 배열이 필요한 트레이드오프를 볼 수 있습니다.
알고리즘
배열
비교
0
교환/쓰기
0
스텝
0/535
읽기
0
보조 메모리
0
재귀 깊이
1/1
재생 속도를 늦추고 '한 단계'로 따라가며 의사코드 하이라이트와 막대 색을 비교해 보세요.
의사코드
mergeSort(lo, hi)
mid ← (lo+hi)/2
mergeSort(lo,mid) mergeSort(mid+1,hi)
while left & right remain
a[k] ← smaller of the two fronts
copy merged run back
시간 복잡도
| 최선 | O(n log n) |
|---|---|
| 평균 | O(n log n) |
| 최악 | O(n log n) |
| 공간 | O(n) |
| 안정 | O |
병합 정렬은 대표적인 분할 정복 알고리즘입니다. 배열을 절반씩 계속 쪼개 원소 하나짜리 구간까지 내려간 뒤, 두 정렬된 구간의 앞 원소끼리 비교하며 작은 쪽부터 꺼내 합칩니다(병합). 막대가 왼쪽 구간부터 순서대로 다시 쓰이는 것이 이 병합 단계입니다.
분할 깊이가 log n이고 각 단계의 병합이 n개를 한 번씩 훑으므로 최선·평균·최악 모두 O(n log n)이 보장됩니다. 입력이 어떤 상태든 성능이 일정하다는 게 퀵 정렬과의 큰 차이입니다.
대신 병합 결과를 담을 임시 배열이 필요해 O(n) 추가 공간을 씁니다. 안정 정렬이라 같은 값의 순서가 유지되고, 연결 리스트나 외부 정렬처럼 순차 접근만 가능한 환경에서도 잘 동작합니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.