partial_sort

template<class RanIt>
    void partial_sort(RanIt first, RanIt middle, RanIt last);
template<class RanIt, class Pred>
    void partial_sort(RanIt first, RanIt middle, RanIt last, Pred pr);

The first template function reorders the sequence designated by iterators in the range [first, last) such that for each N in the range [0, middle - first) and for each M in the range (N, last - first), the predicate !(*(first + M) < *(first + N)) is true. Thus, the smallest middle - 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 ceil((last - first) * log(middle - first)) times, at most.

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

Sample programs: partial_sort and partial_sort (predicate version).