CKTIS / C++
std::stable_sort — stable sorting
std::stable_sort sorts a range while preserving the relative order of elements equivalent under the comparison. It lets you order records by a key without changing the previous order of records with the same key.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::stable_sort(first, last);
std::stable_sort(first, last, comp);std::stable_sort, declared in <algorithm>, rearranges the elements of [first, last) and returns void. The overload without comp sorts in ascending order using the default comparison; the overload with comp uses the supplied comparator. Unlike std::sort, it guarantees preservation of the relative order of equivalent elements.
Equivalence means !comp(a, b) && !comp(b, a), not necessarily a == b. The comparator must define a strict weak ordering: in particular, comp(x, x) must be false, and both the ordering and its induced equivalence must be transitive. Do not use <= instead of < or modify the elements being compared.
Random-access iterators are required, and elements must support swapping, move construction, and move assignment. For N = last - first, the comparison count is O(N log N) when sufficient extra memory is available; otherwise it is at most O(N log² N). Sorting modifies the input but does not guarantee constant auxiliary memory usage.
The example compares only key: B stays before D, and A before C. It is intended to run with a C++23 compiler flag. The displayed code was run unchanged in an isolated environment, and its output matched the stated output. This verification does not attest production runtime compatibility. The linked current working draft may contain extensions beyond C++23; the calls shown do not require them.
Examples
#include <algorithm>
#include <iostream>
#include <vector>
struct Item {
int key;
char id;
};
int main() {
std::vector<Item> items{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};
std::stable_sort(items.begin(), items.end(),
[](const Item& a, const Item& b) {
return a.key < b.key;
});
for (const Item& item : items) {
std::cout << item.key << ' ' << item.id << '\n';
}
}
Result
1 B 1 D 2 A 2 C
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.