C++ <algorithm> - stable_sort() Function

The C++ algorithm::stable_sort function is used to sort the elements in the range [first,last) into increasing order. It is similar to algorithm::sort function except this function preserves the relative order of the elements with equivalent values.

The elements are compared using operator< (in first version) or comp (in second version). Equivalent elements are guaranteed to preserve their original relative order.

Syntax

//default version
template <class RandomAccessIterator>
  void stable_sort (RandomAccessIterator first, RandomAccessIterator last);

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

Parameters

`first`	Specify initial position of the random-access iterator of the sequence to be sorted. The range used is [first,last).
`last`	Specify final position of the random-access iterator of the sequence to be sorted. The range used is [first,last).
`comp`	Specify a binary function that accepts two element as arguments, and returns a value convertible to bool. The returned value indicates whether the first argument is considered to go before the second using the strict weak ordering it defines.

Return Value

None.

Time Complexity

On Average, Linearithmic i.e, Θ(nlog(n)).

Example:

In the example below, the algorithm::stable_sort function is used to sort the given vector.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main (){
  vector<int> Vec= {10, 60, 50, 30, 40, 20};

  cout<<"Vec contains: \n";
  for(int i = 0; i < Vec.size(); i++)
    cout<<Vec[i]<<" ";   

  //sorting the vector
  stable_sort(Vec.begin(), Vec.end());

  cout<<"\n\n";
  cout<<"Sorted Vec contains: \n";
  for(int i = 0; i < Vec.size(); i++)
    cout<<Vec[i]<<" ";   

  return 0;
}

The output of the above code will be:

Vec contains: 
10 60 50 30 40 20 

Sorted Vec contains: 
10 20 30 40 50 60

Example:

The example below shows how to use comp with algorithm::stable_sort function.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool less_than (double i, double j) {
  return ((int)i<(int)j);
}

int main (){
  vector<double> Vec= {1.8, 55.8, 1.5, 55.5, 55.3, 1.3};

  cout<<"Vec contains: \n";
  for(int i = 0; i < Vec.size(); i++)
    cout<<Vec[i]<<" ";   

  //sorting the vector based on the int value of the
  //element, order of equivalent elements are preserved
  stable_sort(Vec.begin(), Vec.end(), less_than);

  cout<<"\n\n";
  cout<<"Sorted Vec contains: \n";
  for(int i = 0; i < Vec.size(); i++)
    cout<<Vec[i]<<" ";   

  return 0;
}

The output of the above code will be:

Vec contains: 
1.8 55.8 1.5 55.5 55.3 1.3 

Sorted Vec contains: 
1.8 1.5 1.3 55.8 55.5 55.3

❮ C++ <algorithm> Library