Menu
I couldn't find any definitive answer to this question.
I suppose most implementation use merge sort that is stable but, is the stability a requirement or a side effect?
996
std::sort requires random access iterators and so cannot be used with list .
std::list::sort. Sorts the elements in ascending order. The order of equal elements is preserved. The first version uses operator< to compare the elements, the second version uses the given comparison function comp .
Stable sorting algorithms preserve the relative order of equal elements, while unstable sorting algorithms don't. In other words, stable sorting maintains the position of two equals elements relative to one another.
std::sort() is a built-in function in C++'s Standard Template Library. The function takes in a beginning iterator, an ending iterator, and (by default) sorts the iterable in ascending order. The function can also be used for custom sorting by passing in a comparator function that returns a boolean.
C++ Standard ISO/IEC 14882:2003 says:
23.2.2.4/31
Notes: Stable: the relative order of the equivalent elements is preserved. If an exception is thrown the order of the elements in the list is indeterminate.
150
Yes, std::list<>::sort is guaranteed to be stable.
See http://www.sgi.com/tech/stl/List.html
39
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
