C++ In a Nutshell

Name

stable_sort function template — Sorts a range in place in stable order

Synopsis

template<typename RandIter>
  void stable_sort(RandIter first, RandIter last);
template<typename RandIter, typename Compare>
  void stable_sort(RandIter first, RandIter last, Compare comp);

The stable_sort function template sorts the range [first, last) in place. The sort is stable, so equivalent elements preserve their original order.

The first version compares items using the < operator. The second version uses comp(X, Y) to test whether X < Y.

Technical Notes

Postcondition: !(*(i + 1) < *i) for all i in [first, last - 1).

Complexity is at most n log n comparisons, in which n = last - first, provided that enough memory is available for temporary results. If memory is limited, the complexity is at most n (log n)² comparisons.

See Also

merge function template, nth_element function template, partial_sort function template, sort function template, sort_heap function template, stable_partition function template