stable_sort

template<class BidIt>
    void stable_sort(BidIt first, BidIt last);
template<class BidIt, class Pred>
    void stable_sort(BidIt first, BidIt last, Pred pr);

The first template function reorders the sequence designated by iterators in the range [first, last) to form a sequence ordered by operator<. It does so without altering the relative order of elements that have equivalent ordering. Thus, the elements are sorted in ascending order.

The function evaluates the ordering predicate X < Y at most ceil((last - first) * (log(last - first))^2) times. (Given enough temporary storage, it can evaluate the predicate at most ceil((last - first) * log(last - first)) times.)

The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).