In C++, how does std::stable_sort differ from std::sort, and what does that difference cost?
answer
- what happens to ties
- relative order of equivalent elements
- a temporary buffer
- N log N vs N log squared N
basics
~20 sstd::stable_sort keeps elements that compare equivalent in their original relative order; std::sort may reorder them. Stability usually costs a temporary buffer and, if that memory is unavailable, up to N log squared N comparisons instead of N log N.
solid answer
~50 sBoth sort a random-access range by a comparator, but only `std::stable_sort` is **stable**: when two elements are equivalent (neither compares less than the other), they keep the relative order they had before the call. `std::sort` gives no such promise, and libc++ and libstdc++ use different introsort variants that may place ties differently. The standard allows `std::sort` `O(N log N)` comparisons; for `std::stable_sort` it allows `N log N` when enough extra memory is available and at most `N log² N` otherwise, which is why implementations try to allocate a temporary buffer and fall back to a slower in-place merge. Stability matters when the input already carries an order you want to keep, such as a leaderboard listed in submission order: sorting by score with `stable_sort` ranks earlier submissions first among ties. `std::sort` is `constexpr` since C++20; `std::stable_sort` becomes `constexpr` only in C++26.
code
cpp · 19 lines#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Entry {
std::string player;
int score;
};
int main() {
// already in submission order: ana submitted first, then bo, cy, di
std::vector<Entry> board{{"ana", 900}, {"bo", 750}, {"cy", 900}, {"di", 900}};
std::stable_sort(board.begin(), board.end(),
[](const Entry& a, const Entry& b) { return a.score > b.score; });
for (const Entry& e : board) std::cout << e.player << ' ' << e.score << '\n';
}go deeper
Know the definition: stable means equivalent elements keep their original relative order, and only std::stable_sort promises it.
Explain equivalence through the comparator, the N log N versus N log squared N bounds, and why stable_sort usually allocates a temporary buffer.
Recognise code that relied on std::sort's tie order by accident, and prefer a complete comparator key when a deterministic order is needed without allocation.
Decide where reproducible ordering is a product requirement and set a rule: explicit tie-breaker keys, or stable_sort where input order is the meaning.
## Equivalent is not the same as equal The sorting algorithms never look at `operator==`. They work with the comparator alone, and two elements `a` and `b` are **equivalent** when `!comp(a, b) && !comp(b, a)`: neither must come before the other. Two leaderboard entries with the same score but different player names are equivalent under a by-score comparator, even though they are clearly different objects. **Stability** is a promise about those equivalent elements: they come out in the same relative order they went in. ## What each algorithm promises | | `std::sort` | `std::stable_sort` | |---|---|---| | Order of equivalent elements | unspecified | preserved | | Comparisons (standard) | `O(N log N)` | `N log N` with enough extra memory, else at most `N log² N` | | Extra memory | none required | typically a temporary buffer | | `constexpr` | since C++20 | since C++26 | | Iterators | random access | random access | Both require the comparator to be a strict weak ordering and both have parallel overloads taking an execution policy since C++17. ## How the implementations get there These are implementation choices, not requirements of the standard: - **libstdc++** implements `std::sort` as introsort (quicksort that switches to heapsort when recursion gets too deep) followed by a final insertion sort. Its `std::stable_sort` requests a `_Temporary_buffer` and runs an adaptive merge sort; when the buffer cannot be obtained it uses an in-place merge, which is where the `N log² N` bound comes from. - **libc++** implements `std::sort` as an introsort that can use a branch-free bitset partition for arithmetic element types in contiguous storage, and its `std::stable_sort` allocates a temporary buffer for ranges above a small threshold and insertion-sorts short ranges. Neither algorithm's tie order is portable for `std::sort`: code that "worked" because ties happened to come out in input order can change when you switch standard library or input size. ## When stability is the requirement Use `std::stable_sort` when the input already carries a meaningful order that the new key should not destroy: 1. **Submission order as tie-breaker.** A leaderboard stored in arrival order, sorted by score with `stable_sort`, ranks the earlier submission first among equal scores. 2. **Multi-pass sorting.** Sorting by the secondary key first and then stable-sorting by the primary key yields a lexicographic order - the classic way UI tables implement "sort by this column, keep the previous one as tie-breaker". 3. **Reproducible output.** Reports, golden-file tests and diffs that must not change between builds. When the elements carry a complete key of their own - score, then a unique player id - you can usually put the tie-breaker into the comparator and use the cheaper `std::sort`, because no two distinct elements are then equivalent. ## The cost in practice - **Allocation.** A temporary buffer means `std::stable_sort` may allocate even though `std::sort` does not. On a hot path or a no-heap embedded target that matters more than the asymptotic bound. - **Moves.** Merge sort moves every element through the buffer and back, so element types with expensive moves pay more. - **Fallback.** If allocation fails the algorithm still completes, just with more comparisons; it does not throw for lack of a buffer. - **No partial version.** `std::partial_sort` and `std::nth_element` are not stable either; there is no stable top-k in `<algorithm>`. ## A worked trace Take a leaderboard stored in submission order: ana 900, bo 750, cy 900, di 900. Sorted by score, highest first: - `std::stable_sort` must produce **ana, cy, di, bo**. The three 900s are equivalent, so they keep their submission order, and bo follows. - `std::sort` must put the three 900s before bo, but may order them in any of six ways. On a handful of elements implementations switch to small special-case sorts that may happen to keep input order, which is exactly how code that depends on it passes small tests and fails on production-sized input. The same reasoning applies to records sorted by a coarse key - a date without a time, a status, a bucket - where large groups of equivalent elements are the norm rather than the exception. The larger the groups, the more visible the difference between the two algorithms, and the more a report that silently reshuffles rows between runs will confuse its readers. ## Choosing quickly Ask whether two elements can be equivalent and whether their order then matters. If not, `std::sort`. If yes and you have a natural extra key, add it to the comparator and still use `std::sort`. If the meaningful order is only the input's position, use `std::stable_sort`.
- How do you get a stable result from std::sort without paying for std::stable_sort?Make sure no two distinct elements are equivalent by adding a unique tie-breaker to the comparator: compare score, then a submission sequence number or player id. With a total order over distinct elements, stability is irrelevant, and `std::sort` gives a deterministic result without allocating a temporary buffer.
- What happens if std::stable_sort cannot allocate its temporary buffer?It still sorts and stays stable. The standard's complexity clause covers exactly this case: `N log N` comparisons with enough extra memory, otherwise at most `N log² N`. libstdc++, for example, falls back to an in-place merge when its temporary buffer request returns less memory than it wanted.
- Saying std::sort keeps equal elements in input order because it did in a test
- Believing stable_sort compares elements with operator== to detect ties
- Claiming std::stable_sort never allocates memory
- Saying std::partial_sort is a stable top-k
- Calling stable_sort just slower with no other difference
Assumes C++23; std::sort is constexpr since C++20 and std::stable_sort becomes constexpr only in C++26.