토픽 8 / 82

병합 정렬 (Merge Sort)

배열을 반으로 나누어 재귀적으로 정렬한 후 병합하는 분할 정복 기반 정렬 알고리즘

목적: 안정적 O(n log n), 대규모 데이터, 예측 가능한 성능

특징: 분할 정복, 안정 정렬, O(n log n) 보장, 외부 메모리

동작: ① 배열을 절반으로 분할(재귀) → ② 크기 1까지 분할 → ③ 병합하며 정렬

병합(Merge): 두 정렬된 배열을 하나로 합치며 정렬, O(n)

시간 복잡도: 최선·평균·최악 O(n log n) - 항상 일정

공간 복잡도: O(n) - 임시 배열 필요

장점: 안정 정렬, O(n log n) 보장, 예측 가능, 대규모 데이터, 외부 정렬(디스크)

단점: O(n) 추가 메모리, 제자리 아님, 소규모에서 오버헤드

적용사례: 대규모 데이터, 외부 정렬, 안정성 필요, 병렬 정렬, Java Arrays.sort(객체)

비교: 병합(안정/O(n)공간/O(n log n)보장) vs 퀵(빠름/제자리/최악O(n²)) vs 힙(제자리/불안정)

연관: 분할 정복, 퀵 정렬, 힙 정렬, 안정 정렬