Standard C++ Library Reference ISO/IEC (VERSION3)

The function evaluates the ordering predicate X < Y at most ceil((last - first) *
log(last - first)) times.
The second template function behaves the same, except that it replaces operator<(X, Y)
with pred(X, Y).
stable_partition
template<class BidIt, class Pr>
BidIt stable_partition(BidIt first, BidIt last,
Pr pred);
The template function reorders the sequence designated by iterators in the range [first,
last) and determines the value K such that for each N in the range [0, K) the predicate
pred(*(first + N)) is true, and for each N in the range [K, last - first) the
predicate pred(*(first + N)) is false. It does so without altering the relative order of
either the elements designated by indexes in the range [0, K) or the elements designated by
indexes in the range [K, last - first). The function then returns first + K.
The predicate must not alter its operand. The function evaluates pred(*(first + N))
exactly last - first times, and swaps at most ceil((last - first) * log(last
- first)) pairs of elements. (Given enough temporary storage, it can replace the swaps with
at most 2 * (last - first) assignments.)
stable_sort
template<class BidIt>
void stable_sort(BidIt first, BidIt last);
template<class BidIt, class Pr>
void stable_sort(BidIt first, BidIt last, Pr pred);
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 a number of times proportional to at most
ceil((last - first) * (log(last - first))^2). (Given enough temporary
storage, it can evaluate the predicate a number of times proportional to at most ceil((last -
first) * log(last - first)).
The second template function behaves the same, except that it replaces operator<(X, Y)
with pred(X, Y).