vehomzzz
vehomzzz

Reputation: 44568

Does std::sort change the relative order of equal elements?

Does the standard guarantee that order of equal elements will not change (eh, forgot the term for that) by using std::sort or do I need to consider an alternative solution to achieve this goal?

Upvotes: 12

Views: 4504

Answers (5)

Jerry Coffin
Jerry Coffin

Reputation: 490108

std::sort is not guaranteed to be stable (the term you were trying to think of). As you'd guess, std::stable_sort is guaranteed to be stable. std::stable_sort also provides a guarantee on worst-case complexity, which std::sort does not. std::sort is typically faster on average though.

Upvotes: 24

Matthieu M.
Matthieu M.

Reputation: 299790

From C++ reference: here

Elements that would compare equal to each other are not guaranteed to keep their original relative order.

You might want stable_sort, but note that it's not as fast (in average)

Upvotes: 3

Todd Gamblin
Todd Gamblin

Reputation: 59827

The term for what you're describing is stability.

From SGI's STL docs:

Note: sort is not guaranteed to be stable.

Use stable_sort if you need this.

Upvotes: 2

JaredPar
JaredPar

Reputation: 754595

No it explicitly does not guarantee this. If you need to maintain relative ordering use stable_sort instead.

Documentation of sort which includes reference to equivalent elements

Upvotes: 2

Naveen
Naveen

Reputation: 73443

No, if you want the guarantee use std::stable_sort

Upvotes: 2

Related Questions