핵심 정리
text
1. 배열을 반으로 나눈다
2. 왼쪽과 오른쪽을 각각 정렬한다
3. 정렬된 두 배열을 하나로 병합한다| 항목 | 특징 |
|---|---|
| 시간 복잡도 | 항상 O(n log n) |
| 공간 복잡도 | 보통 O(n) 추가 배열 |
| 안정성 | 구현에 따라 stable 가능 |
| 핵심 아이디어 | 분할 정복 |
구조
병합 정렬은 문제를 반으로 나누고, 각각을 정렬한 뒤, 두 정렬 결과를 합칩니다. 나누는 깊이는 log n이고, 각 깊이에서 전체 원소를 한 번씩 병합하므로 전체 시간은 O(n log n)입니다.
text
[5, 2, 4, 1]
-> [5, 2] [4, 1]
-> [5] [2] [4] [1]
-> [2, 5] [1, 4]
-> [1, 2, 4, 5]병합
핵심은 이미 정렬된 두 구간을 앞에서부터 비교해 작은 값을 결과 배열에 넣는 과정입니다.
csharp
static int[] Merge(int[] left, int[] right)
{
int[] result = new int[left.Length + right.Length];
int i = 0, j = 0, k = 0;
while (i < left.Length && j < right.Length)
{
if (left[i] <= right[j]) result[k++] = left[i++];
else result[k++] = right[j++];
}
while (i < left.Length) result[k++] = left[i++];
while (j < right.Length) result[k++] = right[j++];
return result;
}<=를 써서 왼쪽 값을 먼저 넣으면 같은 값의 상대 순서를 유지할 수 있어 stable 정렬이 됩니다.
언제 쓰나
| 상황 | 판단 |
|---|---|
| 최악 O(n log n) 보장이 필요 | 병합 정렬 가능 |
| stable 정렬이 중요 | 병합 방식이 유리 |
| 연결 리스트 정렬 | 병합 정렬이 잘 맞음 |
| 추가 메모리가 부담 | 퀵 정렬, 힙 정렬 검토 |
| 표준 API 사용 가능 | 직접 구현보다 API 우선 |
코딩 테스트에서 병합 정렬은 정렬 자체보다 “정렬하며 세기” 문제에서 자주 응용됩니다. 예를 들어 inversion count는 병합 단계에서 오른쪽 값이 먼저 들어갈 때 남은 왼쪽 원소 수를 더하는 방식으로 풀 수 있습니다.
주의할 점
재귀마다 새 배열을 계속 만들면 구현은 쉽지만 할당 비용이 커집니다. 입력이 큰 문제에서는 임시 배열을 재사용하는 구현이 더 안전합니다.
또 병합 정렬의 O(n log n)은 보장되지만, 공간 O(n)을 요구합니다. 메모리 제한이 빡빡한 문제에서는 추가 배열 크기를 먼저 계산하세요.
참고 링크
1 sources