C++ In a Nutshell

Name

partial_sort function template — Sorts the first part of a range

Synopsis

template<typename RandIter>
  void partial_sort(RandIter first, RandIter middle, RandIter last);
template<typename RandIter, typename Compare>
  void partial_sort(RandIter first, RandIter middle, RandIter last, 
                    Compare comp);

The partial_sort function template sorts the initial middle - first elements of the range [first, last) into the range [first, middle). The remaining elements at [middle, last) are not in any particular order.

The first form compares values using the < operator. The second form calls comp(*iter1, *iter2).

See Figure 13-11 for an illustration of the partial-sort algorithm.

Figure 13-11. The partial-sort algorithm

Technical Notes

Postcondition: for all i in [first, middle - 1), *(i + 1) < *i is false, and for all j in [middle, last) and for all i in [first, middle), *j < *i is false.

Complexity is logarithmic, taking about (last - first) × log(middle - first) comparisons.

See Also

nth_element function template, partial_sort_copy function template, partition function template, sort function template