What is the difference between std::sort and std::stable_sort?
algorithm, c++
Solution
Yes, it's as you said, and this is not a concept unique to C++.
Stable sorts preserve the physical order of semantically equivalent values.
`std::sort`:
The order of equal elements is not guaranteed to be preserved. Complexity: `O(N·log(N))`, where `N` = `std::distance(first, last)` comparisons
`std::stable_sort`:
The order of equal elements is guaranteed to be preserved. Complexity: `O(N·log^2(N))`, where `N` = `std::distance(first, last)` applications of `cmp`. If additional memory is available, then the complexity is `O(N·log(N))`.
The implication is that `std::stable_sort` cannot be performed quite as efficiently in terms of execution time, unless "additional memory is available" in which case it is not being performed as efficiently in terms of memory consumption.
Problem
I would like to know how std::sort and std::stable_sort differ with respect to functionality, memory and hardware? The documentation mentions that "Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.", but that didn't make sense to me. What is the "relative order" and "equivalent values"?