Node:Sort, Next:, Previous:Sorting and related operations, Up:Sorting and related operations


Sort

sort (RandomAccessIterator first, RandomAccessIterator last) Function
sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp) Function 

template 
void sort(RandomAccessIterator first, RandomAccessIterator last);

template 
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sort sorts the elements in the range [first, last). It does approximately N \log N (where N equals to last - first) comparisons on the average. If the worst case behavior is important stable_sort or partial_sort should be used.

stable_sort (RandomAccessIterator first, RandomAccessIterator last) Function
stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp) Function 

template 
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template 
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp);

stable_sort sorts the elements in the range [first, last). It is stable, that is, the relative order of the equal elements is preserved. It does at most N(\log N)^2 (where N equals to last - first) comparisons; if enough extra memory is available, it is N \log N.

partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) Function
partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp) Function 

template 
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                  RandomAccessIterator last);

template 
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                  RandomAccessIterator last, Compare comp);

partial_sort places the first middle - first sorted elements from the range [first, last) into the range [first, middle). The rest of the elements in the range [middle, last) are placed in an undefined order. It takes approximately (last - first) * log(middle - first) comparisons.

RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last) Function
RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp) Function 

template 
RandomAccessIterator
    partial_sort_copy(InputIterator first, InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last);

template 
RandomAccessIterator
    partial_sort_copy(InputIterator first, InputIterator last,
                      RandomAccessIterator result_first,
                      RandomAccessIterator result_last, Compare comp);

partial_sort_copy places the first min(last - first, result_last - result_first) sorted elements into the range [result_first, result_first + min(last - first, result_last - result_first)). It returns either result_last or result_first + (last - first) whichever is smaller. It takes approximately (last - first) * log(min(last - first, result_last - result_first)) comparisons.