## stable_sort

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

A templatized algorithm for sorting collections of entities.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### Synopsis

    #include <algorithm>
    template <class RandomAccessIterator>
    void stable_sort (RandomAccessIterator first,
                      RandomAccessIterator last);

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

### Description

The stable_sort algorithm sorts the elements in the range `[first, last)`. The first version of the algorithm uses less than (`<`) as the comparison operator for the sort. The second version uses the comparison function `comp.`

The stable_sort algorithm is considered stable because the relative order of the equal elements is preserved.

### Complexity

stable_sort does at most `N(logN)2` comparisons, where `N` equals `last - first`. If enough extra memory is available, it does at most `NlogN.`

### Example

    //
    // sort.cpp
    //
    #include <vector>
    #include <algorithm>
    #include <functional>
    #include <iostream>
    using namespace std;

    struct associate
     {
    int num;
    char chr;

    associate(int n, char c) : num(n), chr(c) {};
    associate() : num(0), chr(`\0'){};
     };

    bool operator<(const associate &x, const associate &y)
     {
    return x.num < y.num;
     }

    ostream& operator<<(ostream &s, const associate &x)
     {
    return s << "<" << x.num << ";" << x.chr << ">";
     }

    int main ()
     {
    vector<associate>::iterator i, j, k;
    associate arr[20] =
      {associate(-4, ` `), associate(16, ` `),
       associate(17, ` `), associate(-3, `s'),
       associate(14, ` `), associate(-6, ` `),
       associate(-1, ` `), associate(-3, `t'),
       associate(23, ` `), associate(-3, `a'),
       associate(-2, ` `), associate(-7, ` `),
       associate(-3, `b'), associate(-8, ` `),
       associate(11, ` `), associate(-3, `l'),
       associate(15, ` `), associate(-5, ` `),
       associate(-3, `e'), associate(15, ` `)};

    // Set up vectors
    vector<associate> v(arr, arr+20), v1((size_t)20),
                      v2((size_t)20);

    // Copy original vector to vectors #1 and #2
    copy(v.begin(), v.end(), v1.begin());
    copy(v.begin(), v.end(), v2.begin());

    // Sort vector #1
    sort(v1.begin(), v1.end());

    // Stable sort vector #2
    stable_sort(v2.begin(), v2.end());

    // Display the results
    cout << "Original    sort      stable_sort" << endl;
    for(i = v.begin(), j = v1.begin(), k = v2.begin();
      i != v.end(); i++, j++, k++)
      cout << *i << "     " << *j << "     " << *k << endl;

    return 0;
     }

Program Output

    Original    sort      stable_sort
    <-4; >     <-8; >     <-8; >
    <16; >     <-7; >     <-7; >
    <17; >     <-6; >     <-6; >
    <-3;s>     <-5; >     <-5; >
    <14; >     <-4; >     <-4; >
    <-6; >     <-3;e>     <-3;s>
    <-1; >     <-3;s>     <-3;t>
    <-3;t>     <-3;l>     <-3;a>
    <23; >     <-3;t>     <-3;b>
    <-3;a>     <-3;b>     <-3;l>
    <-2; >     <-3;a>     <-3;e>
    <-7; >     <-2; >     <-2; >
    <-3;b>     <-1; >     <-1; >
    <-8; >     <11; >     <11; >
    <11; >     <14; >     <14; >
    <-3;l>     <15; >     <15; >
    <15; >     <15; >     <15; >
    <-5; >     <16; >     <16; >
    <-3;e>     <17; >     <17; >
    <15; >     <23; >     <23; >

### Warnings

If your compiler does not support default template parameters, then you always need to supply the `Allocator` template argument. For instance, you need to write:

`vector<int, allocator>`

instead of:

`vector<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

### See Also

sort,partial_sort, partial_sort_copy

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998