−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,D
TypeScript