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