Sort all elements in the range [ first ... last ). The relative order of equal objects is preserved. The first version uses operator< to compare elements, whereas the second version uses the binary function compare .

Declaration


  
#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 compare
  );

Complexity

Time complexity is O(N(log(N))^2) where N = ( last - first ). If enough memory is available, Time complexity becomes O(N * log(N)). Space complexity is N if enough memory is available; otherwise, space complexity is constant.

Example <ospace/osstd/examples/stblsrt1.cpp>


    #include <iostream>
#include <algorithm>

int array[ 6 ] = { 1, 50, -10, 11, 42, 19 };

void
main()
  {
  stable_sort( array, array + 6 );

  for ( int i = 0; i < 6; ++i )
    cout << array[ i ] << ` `;
  cout << "\n";
  }

-10 1 11 19 42 50

Example <ospace/osstd/examples/stblsrt2.cpp>


    #include <iostream>
#include <string.h>
#include <algorithm>

char* letters[ 6 ] = {"bb", "aa", "ll", "dd", "qq", "cc" };

bool
string_less( const char* a_, const char* b_ )
  {
  return ::strcmp( a_, b_ ) < 0 ? 1 : 0;
  }

void
main()
  {
  stable_sort( letters, letters + 6, string_less );

  for ( int i = 0; i < 6; ++i )
    cout << letters[ i ] << ` `;
  cout << "\n";
  }

aa bb cc dd ll qq

stable_sort

Library

Declaration

Complexity

Example <ospace/osstd/examples/stblsrt1.cpp>

Example <ospace/osstd/examples/stblsrt2.cpp>