 

Category: algorithms   Component type: function 
Prototype
Partial_sort
is an overloaded name; there are actually two partial_sort
functions.
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);
Description
Partial_sort
rearranges the elements in the range [first, last)
so that they are partially in ascending order. Specifically, it places the smallest middle  first
elements, sorted in ascending order, into the range [first, middle)
. The remaining last  middle
elements are placed, in an unspecified order, into the range [middle, last)
. [1] [2]
The two versions of partial_sort
differ in how they define whether one element is less than another. The first version compares objects using operator<
, and the second compares objects using a functors comp
.
The postcondition for the first version of partial_sort
is as follows. If i
and j
are any two valid iterators in the range [first, middle)
such that i
precedes j
, and if k
is a valid iterator in the range [middle, last)
, then *j < *i
and *k < *i
will both be false
. The corresponding postcondition for the second version of partial_sort
is that comp(*j, *i)
and comp(*k, *i)
are both false. Informally, this postcondition means that the first middle  first
elements are in ascending order and that none of the elements in [middle, last)
is less than any of the elements in [first, middle)
.
Definition
Defined in the standard header algorithm, and in the nonstandard backwardcompatibility header algo.h.
Requirements on types
For the first version:

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

RandomAccessIterator
's value type is LessThanComparable.

The ordering relation on
RandomAccessIterator
's value type is a strict weak ordering, as defined in the LessThanComparable requirements.
For the second version:

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

StrictWeakOrdering
is a model of StrictWeakOrdering.

RandomAccessIterator
's value type is convertible to StrictWeakOrdering
's argument type.
Preconditions

[first, middle)
is a valid range.

[middle, last)
is a valid range.
(It follows from these two conditions that [first, last)
is a valid range.)
Complexity
Approximately (last  first) * log(middle  first)
comparisons.
Example
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
partial_sort(A, A + 5, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
Notes
[1] Note that the elements in the range [first, middle)
will be the same (ignoring, for the moment, equivalent elements) as if you had sorted the entire range using sort(first, last)
. The reason for using partial_sort
in preference to sort
is simply efficiency: a partial sort, in general, takes less time.
[2] partial_sort(first, last, last)
has the effect of sorting the entire range [first, last)
, just like sort(first, last)
. They use different algorithms, however: sort
uses the introsort algorithm (a variant of quicksort), and partial_sort
uses heapsort. See section 5.2.3 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. AddisonWesley, 1975.), and J. W. J. Williams (CACM 7, 347, 1964). Both heapsort and introsort have complexity of order N log(N)
, but introsort is usually faster by a factor of 2 to 5.
See also
partial_sort_copy
, sort
, stable_sort
, binary_search
, lower_bound
, upper_bound
, less<T>
, StrictWeakOrdering, LessThanComparable