Is the `std::sort` function unstable?

Question

Just wanted to confirm if what I am thinking is right or wrong. According to the definition:

A sorting algorithm is said to be stable if two objects with equal or same keys appear in the same order in sorted output as they appear in the input array to be sorted.

Now in std::sort in the standard library, returning false when two elements are equal is a must. Hence, is it safe to say that the sorting algorithm used is unstable?

[What's the difference between “STL” and “C++ Standard Library”?](https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library) — François Andrieux, Dec 08 '20 at 15:15
As far as I know, nobody has discovered or invented an O(n*log(n)) in-place stable sorting algorithm yet. — molbdnilo, Dec 08 '20 at 15:23
@molbdnilo I think [this](https://en.wikipedia.org/wiki/Merge_sort#Variants) mentions some. And is `std::sort` guaranteed in-place, or why did you say that? — superb rain, Dec 08 '20 at 21:00

score 4 · Accepted Answer · edited Dec 08 '20 at 15:18

Now in the sort function in STL, returning false when two elements are equal is a must. Hence, is it safe to say that the sorting algorithm used is unstable?

No, that’s completely unrelated.

As a matter of fact, std::sort isn’t guaranteed to be stable; if you require a stable sort, use std::stable_sort.

But the string weak ordering requirement is unrelated, and is the same for both std::sort and std::stable_sort.

score 2 · Answer 2 · edited Dec 08 '20 at 15:17

2

std::sort() is not guaranteed to be stable, and in practice it will never be implemented as stable since stable sort is slower. If you need stable sort, use std::stable_sort().

edited Dec 08 '20 at 15:17

François Andrieux

28,148
6
56
87

answered Dec 08 '20 at 15:15

Eugene

6,194
1
20
31

score 2 · Answer 3 · answered Dec 08 '20 at 15:16

returning false when two elements are equal is a must.

That doesn't make the difference between a stable and a non-stable sorting algorithm.

The two major standard sorting algorithms are std::sort and std::stable_sort. The first is not guaranteed to be stable, the latter is. Both require < or the comparator that is used as predicate to implement a strict weak ordering (which implies a < a is false for any a).

score -2 · Answer 4 · answered Dec 08 '20 at 15:24

-2

Check the C++ reference at http://www.cplusplus.com/reference/algorithm/sort/ which clearly indicates it to be not stable

answered Dec 08 '20 at 15:24

TKA

183
2
4

It’s unstable, but not for the reason OP thinks. – Konrad Rudolph Dec 08 '20 at 15:34
assume OP did consult documentation before asking, then this answer will not help them. If you assume that they didn't then this should have been a comment – 463035818_is_not_an_ai Dec 08 '20 at 15:37

Is the `std::sort` function unstable?

4 Answers4