Source code
Declaration
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template <class RandomAccessIterator>
inline void stable_sort(RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
inline void stable_sort(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator, class Compare>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);
Description The sort functions sort the elements in the range [ first, last) , but does not preserve the order of equal elements. The first sort function determines the ordering using operator< and the second sort function determines the ordering using the function object comp.
The stable_sort functions sort the elements in the range [ first, last) , preserving the relative ordering of equal elements. The first stable_sort function determines the ordering using operator< and the second stable_sort function determines the ordering using the function object comp.
The partial_sort functions sorts the elements in the range [ first, last) \ to the extent that the range [ first, middle) contains the first n elements of the fully sorted sequence, where n is the size of the range [ first, middle) . The elements in the range [ middle, last) are placed in an undefined order. The first partial_sort function determines the ordering using operator< and the second partial_sort function determines the ordering using the function object comp.
The partial_sort_copy functions place the first n sorted elements from the range [ first, last) into the range of size n beginning at result_first, where n is the smaller size of the ranges [ first, last) and [ result_first, result_last) . The contents of the range [ first, last) remain unchanged. The first partial_sort_copy function determines the ordering using operator< and the second partial_sort_copy function determines the ordering using the function object comp.
Type requirements
Group Sorting and related operations
Time complexity 
average for the sort functions, at most
for the stable_sort functions, and 
for
the partial_sort and partial_sort_copy functions, where n is the size of the range [ first, last)
.
For the partial_sort functions, m is the size of the range
[ middle, last)
. For the partial_sort_copy functions,
m is the smaller size of the ranges [ first, last)
and
[ result_first, result_last)
.
The sort functions make 
comparisons on the average. In
the worst case, it takes 
time and makes 
comparisons.
If the worst case behavior is important, then the stable_sort or
partial_sort functions should be used.
The stable_sort functions make at most 
comparisons.
However, if enough memory is available for the buffer required by the adaptive
version of the algorithm, the time and number of comparisons are
.
The partial_sort functions make approximately 
comparisons.
The partial_sort_copy functions make approximately 
comparisons.
Space complexity Logarithmic for the sort functions, at most linear for the stable_sort functions, and constant for the partial_sort and partial_sort_copy functions.
The sort functions require 
space for recursive
calls, where n is the size of the range [ first, last)
.
The stable_sort functions require linear space for buffer if the adaptive algorithm is used and the buffer is large enough to have half of the sequence placed in it, otherwise logarithmic space is required for recursive function calls (linear space may also be used for some buffer size that is not large enough to contain half of the sequence).
The partial_sort functions and the partial_sort_copy functions require constant space.
Mutative? Yes.
Example Select here to view the source code for the example.
Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.