병합 정렬
개요
병합 정렬(merge sort)은 구간을 절반씩 나누어 각각 정렬한 뒤, 이미 정렬된 두 구간을 합쳐 전체 순서를 완성하는 분할 정복 정렬이다. 날짜순으로 정리된 두 문서 묶음을 하나로 합칠 때, 양쪽 맨 앞 문서의 날짜만 비교해 더 이른 쪽을 차례로 꺼내면 뒤쪽 문서를 다시 뒤질 필요가 없는 것과 같은 원리다.
연혁
John von Neumann은 1945년 EDVAC 내부 정렬 프로그램 원고에서 병합 정렬을 고안했다. Donald Knuth는 1970년 논문 「Von Neumann’s First Computer Program」에서 이 자필 원고를 분석하며, 작은 정렬 열을 차례로 합쳐 긴 정렬 열을 만드는 루틴과 명령어 구성을 복원했다.1 이후 Herman H. Goldstine과 von Neumann은 1948년 보고서 *Planning and Coding of Problems for an Electronic Computing Instrument*에서 이 절차를 정식 순서도와 귀납적 검증으로 정리했다.2
분할과 안정 병합
원소가 0개이거나 1개인 구간은 그 자체로 이미 정렬되어 있다. 길이 인 구간 를 중간점 를 기준으로 왼쪽 와 오른쪽 로 반씩 나누어 재귀적으로 정렬한 뒤, 두 정렬 구간의 맨 앞 원소를 비교하며 보조 배열에 합친다. 길이 인 배열을 정렬하는 수행 시간 은 다음 점화식을 따른다.
정렬 키가 같은 두 레코드가 입력에서의 상대 순서를 정렬 후에도 그대로 유지하는 성질을 안정성(stability)이라 한다. 왼쪽 구간 에 속한 원소는 오른쪽 구간 의 원소보다 원래 입력에서 앞에 있었으므로, 병합 중 두 원소의 키가 같을 때() 왼쪽 원소를 먼저 꺼내면 안정성이 보장된다. 만약 이 비교를 등호가 빠진 < 0으로 바꾸면 동률에서 오른쪽 원소가 먼저 나가 순서가 뒤집힌다.
실행 예제
C++20
C++20판도 key가 같은 레코드의 입력 순서를 보존한다. 비교 함수는 앞섬·동률·뒤섬을 음수·0·양수로 반환한다. 값을 복사할 수 있는 레코드를 작업 배열로 받아 버퍼를 재사용하므로 호출자의 원본은 유지된다.
#include <cstddef>
#include <iostream>
#include <vector>
template<class T, class Compare>
void sortRange(std::vector<T>& values, std::vector<T>& buffer,
std::size_t lo, std::size_t hi, Compare compare) {
if (hi - lo <= 1) return;
const auto mid = lo + (hi - lo) / 2;
sortRange(values, buffer, lo, mid, compare);
sortRange(values, buffer, mid, hi, compare);
auto left = lo;
auto right = mid;
for (auto out = lo; out < hi; ++out) {
// 동률에서 왼쪽을 먼저 고르면 같은 키의 입력 순서를 지킨다.
if (left < mid && (right == hi || compare(values[left], values[right]) <= 0)) {
buffer[out] = values[left++];
} else {
buffer[out] = values[right++];
}
}
for (auto i = lo; i < hi; ++i) values[i] = buffer[i];
}
template<class T, class Compare>
std::vector<T> mergeSort(std::vector<T> values, Compare compare) {
// 값으로 받은 작업 배열과 복사한 버퍼를 쓰므로 호출자의 배열은 보존된다.
auto buffer = values;
sortRange(values, buffer, 0, values.size(), compare);
return values;
}
struct Record { int key; char id; };
int main() {
const std::vector<Record> records{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};
const auto result = mergeSort(records, [](const Record& a, const Record& b) {
return (a.key > b.key) - (a.key < b.key);
});
for (std::size_t i = 0; i < result.size(); ++i) {
if (i != 0) std::cout << ',';
std::cout << result[i].id;
}
std::cout << '\n';
for (std::size_t i = 0; i < records.size(); ++i) {
if (i != 0) std::cout << ',';
std::cout << records[i].id;
}
std::cout << '\n';
return 0;
}B,D,A,C
A,B,C,DTypeScript
단순한 숫자 배열만 정렬하면 값이 같은 원소끼리 자리가 바뀌었는지 구별할 수 없다. 아래 예제는 정렬 기준인 key와 식별자 id를 함께 담은 레코드 네 개를 정렬해 안정성을 확인한다. 비교 함수 compare(a, b)는 a가 앞설 때 음수, 같을 때 0, 뒤설 때 양수를 돌려주는 일관된 전순서(total preorder) 규칙을 따라야 한다.
function mergeSort<T>(input: readonly T[], compare: (a: T, b: T) => number): T[] {
const values = [...input];
const buffer = new Array<T>(values.length);
function sort(lo: number, hi: number): void {
if (hi - lo <= 1) return;
const mid = lo + Math.floor((hi - lo) / 2);
sort(lo, mid);
sort(mid, hi);
let left = lo;
let right = mid;
for (let out = lo; out < hi; out++) {
// 왼쪽이 앞서거나 동률이면 왼쪽을 꺼내며, 동률에서 입력 순서가 보존된다.
if (left < mid && (right >= hi || compare(values[left]!, values[right]!) <= 0)) {
buffer[out] = values[left++]!;
} else {
buffer[out] = values[right++]!;
}
}
for (let i = lo; i < hi; i++) values[i] = buffer[i]!;
}
sort(0, values.length);
return values;
}
const records = [
{ key: 2, id: 'A' }, { key: 1, id: 'B' },
{ key: 2, id: 'C' }, { key: 1, id: 'D' },
];
const result = mergeSort(records, (a, b) => a.key - b.key);
console.log(result.map(item => item.id).join(','));
console.log(records.map(item => item.id).join(','));B,D,A,C
A,B,C,Dkey가 1인 B와 D가 앞에 오되 입력 순서대로 B가 먼저 나오고, key가 2인 A와 C도 A가 앞선다. 매 재귀 호출마다 임시 배열을 새로 할당하면 가비지 컬렉션 부담이 커지므로, 여기서는 길이 짜리 buffer 하나를 미리 잡아 모든 병합 단계에서 재사용한다.
비용과 실무 경계
비교 한 번이 일 때, 입력 분포와 무관하게 최선·평균·최악 모두 시간에 동작한다. 분할 깊이가 이고 각 깊이에서 합계 개의 원소를 처리하기 때문이다. 공간 복잡도는 보조 버퍼 과 재귀 호출 스택 을 합쳐 이다.
퀵 정렬과 달리 최악 입력에서도 으로 느려지지 않고 안정성을 지킨다는 점이 강점이지만, 배열에서는 추가 메모리가 필요하다. 반면 단일·이중 연결 리스트에서는 노드 포인터만 이어 붙이면 되므로 보조 배열 없이 작업 공간으로 병합할 수 있고, 디스크·테이프처럼 순차 읽기가 중요한 외부 정렬(external merge sort)의 기본 골격으로도 쓰인다. 이미 정렬된 연속 구간(natural runs)을 살려 합치는 Timsort 같은 적응형 병합 정렬은 정렬된 입력을 에 처리한다. Java는 객체 배열 정렬과 기본형 배열 정렬의 구현을 구분한다. CPython과 V8의 현행 main 소스는 런을 합치는 순서를 정하는 Powersort 전략을 설명하므로, 언어 전체의 정렬을 한 알고리즘 이름으로 묶기보다 API와 버전을 함께 확인하는 편이 정확하다.3
같이 보기
각주
- Donald E. Knuth, “Von Neumann’s First Computer Program,” ACM Computing Surveys 2(4), 1970, pp.247–260, 특히 p.253 “The Sorting Program”. 원문 스캔, DOI. ↩
- Herman H. Goldstine, John von Neumann, Planning and Coding of Problems for an Electronic Computing Instrument, Part II, Vol. II, Institute for Advanced Study, 1948-04-15, §11.3–11.4. IAS original. ↩
- Oracle Java SE 25, Arrays: object sort and primitive sort implementation notes. API. CPython listsort.txt; V8 array-sort.tq. Main-source observations checked 2026-11-07. ↩