You don't always need a full
sort ; you usually need less, and rarely you need more. In general order from cheapest to most expensive, your standard sorting algorithm options are:
partition, stable_partition, nth_element, partial_sort (with its variant
partial_sort_copy ),
sort , and
stable_sort . Use the least expensive one that does the work you actually need; using a more powerful one is wasteful.
partition, stable_partition , and
nth_element run in linear time, which is nice.
nth_element, partial_sort, sort , and
stable_sort require random-access iterators. You can't use them if you have only bidirectional iterators (e.g.,
list<T>::iterator s). If you need these algorithms but you don't have random-access iterators, consider using the index container idiom: Create a container that does support random-access iterators (e.g., a
vector ) of iterators into the range you have, and then use the more powerful algorithm on that using a dereferencing version of your predicate (one that dereferences the iterators before doing its usual comparison).
Use the
stable_… versions only if you need to preserve the relative ordering of equal elements. Note that
partial_sort and
nth_element aren't stable (meaning that they don't keep equivalent elements in the same relative order they were in before the sort), and they have no standardized stable versions. If you otherwise want these algorithms but need stability, you probably want
stable_sort .
Of course, don't use any sorting algorithm at all if you don't have to: If you are using a standard associative container (
set /
multiset or
map /
multimap ) or the
priority_queue adapter, and only need one sort order, the elements in the container stay sorted all the time.