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

void partial_sort(RanIt first, RanIt mid,
RanIt last, Pr pred);
The first template function reorders the sequence designated by iterators in the range [first,
last) such that for each N in the range [0, mid - first) and for each M in the range
(N, last - first) the predicate !(*(first + M) < *(first + N)) is true.
Thus, the smallest mid - first elements of the entire sequence are sorted in ascending
order, ordered by operator<. The order of the remaining elements is otherwise unspecified.
The function evaluates the ordering predicate X < Y a number of times proportional to at most
ceil((last - first) * log(mid - first)).
The second template function behaves the same, except that it replaces operator<(X, Y)
with pred(X, Y).
partial_sort_copy
template<class InIt, class RanIt>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2);
template<class InIt, class RanIt, class Pr>
RanIt partial_sort_copy(InIt first1, InIt last1,
RanIt first2, RanIt last2, Pr pred);
The first template function determines K, the number of elements to copy as the smaller of
last1 - first1 and last2 - first2. It then copies and reorders K elements of the
sequence designated by iterators in the range [first1, last1) such that the K elements
copied to first2 are ordered by operator<. Moreover, for each N in the range [0, K) and
for each M in the range (0, last1 - first1) corresponding to an uncopied element, the
predicate !(*(first2 + M) < *(first1 + N)) is true. Thus, the smallest K elements
of the entire sequence designated by iterators in the range [first1, last1) are copied and
sorted in ascending order to the range [first2, first2 + K).
The function evaluates the ordering predicate X < Y a number of times proportional to at most
ceil((last - first) * log(K)).
The second template function behaves the same, except that it replaces operator<(X, Y)
with pred(X, Y).
partition
template<class BidIt, class Pr>
BidIt 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