CODEWITHSUNDEEP
c++sortingc++17std
harsh
harsh

Reputation: 83

Is the `std::sort` function unstable?

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?

Upvotes: 1

Views: 1871

Answers (4)

TKA
TKA

Reputation: 183

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

Upvotes: -2

Konrad Rudolph
Konrad Rudolph

Reputation: 545508

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.

Upvotes: 5

Eugene
Eugene

Reputation: 7160

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().

Upvotes: 2

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122133

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).

Upvotes: 2

Related Questions