+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