병합정렬: 안정성과 일관된 성능을 갖춘 분할 정복 정렬
병합정렬의 분할 정복 구조, 안정 정렬 특성, 시간복잡도와 외부 정렬·연결 리스트 환경에서의 활용 방법을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
대용량 데이터나 외부 정렬처럼 입력 상태에 따른 성능 흔들림을 줄여야 하는 경우, 병합정렬은 비교 기반 정렬 가운데 예측 가능한 선택지다. 최악·평균·최선 시간복잡도가 모두 O(n log n)이며, 같은 키를 가진 레코드의 기존 순서도 유지한다. 일부 수험 자료에서 최악 O(n^2)로 언급되기도 하지만, 병합정렬의 최악 시간복잡도는 O(n log n)이다.
배열을 나누고 정렬된 구간을 합치는 방식
병합정렬은 분할 정복(Divide and Conquer)을 이용한다. 배열을 반으로 쪼갠 뒤 각 부분을 정렬하고, 정렬이 끝난 두 구간을 하나로 병합한다. 이 과정을 더 이상 나눌 수 없는 구간까지 반복한다.
동일 키 원소의 상대적 순서를 지키는 안정 정렬(Stable Sorting)이라는 점도 특징이다. 병합 단계에서 값이 같다면 좌측 구간의 원소를 먼저 선택하면 안정성이 유지된다.
구현은 크게 두 형태로 나뉜다.
- Top-Down은 재귀 호출로 분할과 병합을 수행한다.
- Bottom-Up(2원 병합정렬)은 길이 1인 구간부터 인접 구간을 합치며, 구간 길이를 2배씩 확장한다. R=ceil(log2 n)회 반복한다.
재귀형 병합의 흐름과 경계 조건
재귀 호출의 종료 조건은 low < high다. 이 조건이 성립하지 않으면 반환한다. 중간 위치는 mid = low + (high - low) / 2처럼 계산해 오버플로를 피할 수 있다.
병합마다 임시 버퍼를 새로 만들기보다, 한 번 할당한 버퍼를 재사용하는 편이 낫다. 동적 할당을 반복하지 않아도 된다.
성능 보장 대신 메모리를 사용하는 선택
병합정렬은 최악·평균·최선에서 O(n log n)을 보장한다. 비교 기반 정렬의 하한인 O(n log n)에 가까운 성능을 일관되게 제공하지만, 병합을 위한 추가 메모리 O(n)이 필요하다. 메모리 제약이 큰 환경에서는 이 비용이 선택 기준이 된다.
입력 상태에 따라 실행 경로가 크게 달라지지 않아 결과 재현성도 높다. 특히 외부 정렬에서는 디스크나 네트워크 I/O 기반의 k-way merge와 연결하기 쉽다. 메모리 한계 안에서 큰 런(run)을 만들고, 이를 다단 병합하는 방식으로 확장할 수 있다.
Top-Down은 구현이 단순한 대신 재귀 스택을 사용한다. Bottom-Up은 반복문을 기반으로 하므로 재귀 스택을 쓰지 않으며, 일정한 순서로 접근해 캐시 지역성과 스택 사용량 측면에서 장점이 있다.
외부 정렬과 연결 리스트에서의 활용
대규모 로그나 거래 데이터를 외부 정렬할 때는 입력을 나눠 메모리 안에서 정렬된 런을 만들고, k-way 병합으로 이어지는 파이프라인을 구성할 수 있다. 이 과정에서는 장애에 대비한 체크포인트와 임시 파일 정리 정책도 함께 운영한다.
연결 리스트는 랜덤 접근 비용이 크므로 병합정렬이 적합한 선택이 될 수 있다. 리스트를 나누고 합치는 작업은 O(1) 보조 공간으로 수행할 수 있다.
분할 단계는 멀티스레드로 병렬화할 수 있다. 스레드 풀에서 작업을 실행하고 마지막 병합 단계의 작업량을 균형 있게 배분한다. NUMA 환경에서는 구간을 고정하고 바인딩해 캐시 친화성을 확보할 수 있다.
다른 비교 정렬과의 차이
| 알고리즘 | 성능(평균) | 성능(최악) | 안정성(Stable) | 외부정렬 적합성 | 추가 메모리 |
|---|---|---|---|---|---|
| 병합정렬 | O(n log n) | O(n log n) | 예 | 매우 높음 | O(n) |
| 퀵정렬 | O(n log n) | O(n^2) | 아니오 | 낮음 | 평균 O(log n) 스택 |
| 힙정렬 | O(n log n) | O(n log n) | 아니오 | 낮음 | O(1) |
| 삽입정렬 | O(n^2) | O(n^2) | 예 | 매우 낮음 | O(1) |
| 버블정렬 | O(n^2) | O(n^2) | 예 | 매우 낮음 | O(1) |
C에서 구현하는 재귀형 병합정렬
정수 배열을 정렬하고 임시 버퍼를 한 번만 할당해 재사용하는 예제다. 환경은 C17과 gcc/clang을 전제로 한다.
컴파일 예: gcc -O2 -std=c17 mergesort.c -o mergesort
// mergesort.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void merge(int *a, int *tmp, int low, int mid, int high) {
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
// 안정성 보장: 좌측 우선 tie-break
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= high) tmp[k++] = a[j++];
// 병합 결과를 원배열에 복사
memcpy(a + low, tmp + low, (size_t)(high - low + 1) * sizeof(int));
}
static void mergesort_rec(int *a, int *tmp, int low, int high) {
if (low >= high) return;
int mid = low + (high - low) / 2;
mergesort_rec(a, tmp, low, mid);
mergesort_rec(a, tmp, mid + 1, high);
// 이미 정렬된 경우 스킵 최적화(약한 최적화)
if (a[mid] <= a[mid + 1]) return;
merge(a, tmp, low, mid, high);
}
void mergesort(int *a, int n) {
int *tmp = (int*)malloc(sizeof(int) * (size_t)n);
if (!tmp) { fprintf(stderr, "temp buffer alloc failed\n"); exit(1); }
mergesort_rec(a, tmp, 0, n - 1);
free(tmp);
}
int main(void) {
int a[] = {7, 3, 5, 2, 9, 1, 4, 8, 6, 0};
int n = (int)(sizeof(a) / sizeof(a[0]));
mergesort(a, n);
for (int i = 0; i < n; ++i) printf("%d%c", a[i], (i+1==n)?'\n':' ');
return 0;
}안정 정렬을 유지하려면 a[i] <= a[j] 비교를 사용해야 한다. 인접한 두 구간이 이미 정렬된 상태라면 병합을 건너뛸 수 있고, 임시 버퍼를 한 번만 할당하면 동적 메모리 오버헤드도 줄일 수 있다.
반복형 병합으로 재귀 스택을 없애기
Bottom-Up 방식은 width=1에서 시작해 서로 이웃한 두 블록을 병합한다. 반복마다 width = width × 2로 늘어나며, 배열 A와 크기 n이 주어졌을 때 [i..i+width-1], [i+width..i+2*width-1] 구간을 병합한다.
마지막 단계에서는 블록 길이가 균등하지 않을 수 있으므로 별도 처리 로직이 필요하다. 대신 재귀 스택을 사용하지 않고 일정한 패턴으로 순차 접근할 수 있다.
void mergesort_bottom_up(int *a, int n) {
int *tmp = (int*)malloc(sizeof(int) * (size_t)n);
if (!tmp) { fprintf(stderr, "alloc fail\n"); exit(1); }
for (int width = 1; width < n; width <<= 1) {
for (int i = 0; i < n; i += (width << 1)) {
int low = i;
int mid = i + width - 1;
int high = (i + (width << 1) - 1 < n-1) ? (i + (width << 1) - 1) : (n - 1);
if (mid >= high) continue; // 오른쪽 구간 없음
// 이미 정렬된 경우 스킵
if (a[mid] <= a[mid + 1]) continue;
merge(a, tmp, low, mid, high);
}
}
free(tmp);
}예시로 n=10이면 R=ceil(log2 10)=4회 반복 수행한다.
일관된 정렬 비용이 필요한 상황
병합정렬은 O(n log n)의 시간복잡도를 일관되게 보장하므로 최악 성능이 하락하지 않는다. 외부 정렬에서는 런 크기 L과 k-way 병합을 기준으로 파스 수가 약 log_k(총 런 수)가 되며, I/O 총량을 최소화하는 경향이 있다.
추가 메모리 O(n)을 수용할 수 있다면, 안정성·결과 재현성·외부 정렬 적합성이 필요한 대규모 데이터 처리와 연결 리스트 정렬에서 우선 검토할 수 있다. 입력 특성에 맞춰 Top-Down과 Bottom-Up(2원 병합정렬)을 고르고, 임시 버퍼 재사용과 정렬된 구간 생략을 적용하면 구현 단순성과 검증 용이성, 코드 유지보수성을 함께 확보할 수 있다.