# Man Page stable_sort.3

```
Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.

```

## NAME

```     stable_sort

- A templatized algorithm for sorting collections of  enti-
ties.

```

## 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  parame-
ters,  then you always need to supply the Allocator template
argument. For instance, you need to write:

vector<int, allocator>

vector<int>
If your compiler does not support namespaces,  then  you  do
not need the using declaration for std.

```

```     sort, partial_sort, partial_sort_copy

```