Sorting Algorithms

There are two fundamental sorting algorithms provided by the standard library, described as follows:

void sort (RandomAccessIterator first, 
       RandomAccessIterator last [, Compare ] );
 
 void stable_sort (RandomAccessIterator first, 
       RandomAccessIterator last [, Compare ] );
 

The sort() algorithm is slightly faster, but it does not guarantee that equal elements in the original sequence will retain their relative orderings in the final result. If order is important, then use the stable_sort() version.

Because these algorithms require random access iterators, they can be used only with vectors, deques, and ordinary C pointers. Note, however, that the list container provides its own sort() member function.

The comparison operator can be explicitly provided when the default operator < is not appropriate. This is used in the example program to sort a list into descending, rather than ascending order. An alternative technique for sorting an entire collection in the inverse direction is to describe the sequence using reverse iterators.

More Sorts

The following example program illustrates the sort() algorithm being applied to a vector, and the sort() algorithm with an explicit comparison operator being used with a deque.

void sort_example () 
    // illustrate the use of the sort algorithm
 {
       // fill both a vector and a deque
       // with random integers
    vector<int> aVec(15);
    deque<int> aDec(15);
    generate (aVec.begin(), aVec.end(), randomValue);
    generate (aDec.begin(), aDec.end(), randomValue);
    
       // sort the vector ascending
    sort (aVec.begin(), aVec.end());
    
       // sort the deque descending
    sort (aDec.begin(), aDec.end(), greater<int>() );
 
       // alternative way to sort descending
    sort (aVec.rbegin(), aVec.rend());
 }