병합 정렬
개요
병합 정렬(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으로 바꾸면 동률에서 오른쪽 원소가 먼저 나가 순서가 뒤집힌다.
실행 예제
단순한 숫자 배열만 정렬하면 값이 같은 원소끼리 자리가 바뀌었는지 구별할 수 없다. 아래 예제는 정렬 기준인 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++) {
// 동률(compare <= 0)일 때 왼쪽 구간 원소를 먼저 꺼내 입력 순서를 보존한다.
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 하나를 미리 잡아 모든 병합 단계에서 재사용한다.
C++ 예제
C++ 표준 라이브러리 관례에서는 비교 함수가 3방향 정수 대신 엄격한 약순서(strict weak ordering, comp(a, b)가 a < b일 때만 참)를 받는다. 이때 동률에서 왼쪽 원소를 먼저 꺼내려면 "오른쪽 원소가 왼쪽 원소보다 엄격히 앞서는가"를 뜻하는 comp(values[right], values[left])가 거짓(!comp(right, left))일 때 왼쪽을 선택하면 std::stable_sort와 동일한 안정 병합이 된다.
#include <cstddef>
#include <functional>
#include <iostream>
#include <vector>
struct Record {
int key;
char id;
};
template <typename T, typename Compare>
std::vector<T> mergeSort(const std::vector<T>& input, Compare comp) {
std::vector<T> values = input;
std::vector<T> buffer(values.size());
auto sort = [&](auto& self, std::size_t lo, std::size_t hi) -> void {
if (hi - lo <= 1) return;
std::size_t mid = lo + (hi - lo) / 2;
self(self, lo, mid);
self(self, mid, hi);
std::size_t left = lo;
std::size_t right = mid;
for (std::size_t out = lo; out < hi; ++out) {
// 오른쪽 원소가 엄격히 앞설 때(!comp(right, left))만 오른쪽을 꺼내 안정성을 지킨다.
if (left < mid && (right >= hi || !comp(values[right], values[left]))) {
buffer[out] = values[left++];
} else {
buffer[out] = values[right++];
}
}
for (std::size_t i = lo; i < hi; ++i) values[i] = buffer[i];
};
sort(sort, 0, values.size());
return values;
}
void printIds(const std::vector<Record>& items) {
for (std::size_t i = 0; i < items.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << items[i].id;
}
std::cout << '\n';
}
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; });
printIds(result);
printIds(records);
return 0;
}실행 결과:
B,D,A,C
A,B,C,D비용과 실무 경계
비교 한 번이 일 때, 입력 분포와 무관하게 최선·평균·최악 모두 시간에 동작한다. 분할 깊이가 이고 각 깊이에서 총 개의 원소를 스캔하기 때문이다. 공간 복잡도는 보조 버퍼 과 재귀 호출 스택 을 합쳐 이다.
퀵 정렬과 달리 최악 입력에서도 으로 느려지지 않고 안정성을 지킨다는 점이 강점이지만, 배열에서는 추가 메모리가 필요하다. 반면 단일·이중 연결 리스트에서는 노드 포인터만 이어 붙이면 되므로 보조 배열 없이 작업 공간으로 병합할 수 있고, 디스크·테이프처럼 순차 읽기가 중요한 외부 정렬(external merge sort)의 기본 골격으로도 쓰인다. 또한 입력에 이미 정렬된 연속 구간(natural runs)이 많은 실무 데이터에서는, 이를 그대로 살려 합치는 변형인 Timsort가 최선 에 수렴해 Python·Java·V8 표준 정렬로 채택되어 있다.
같이 보기
각주
- 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. 2, Institute for Advanced Study, 1948, §7.6–7.8. ↩