Difference Between std::sort() and std::stable_sort()

std::sort() and std::stable_sort() are both sorting algorithms provided by the C++ standard library, but they have different characteristics and use cases.

Using std::sort()

std::sort() is a highly efficient, non-stable sorting algorithm. It sorts the elements in the range [first, last) into ascending order by default, but you can provide a custom comparator to change the sorting criteria.

Here's an example using std::sort():

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> numbers{3, 1, 4, 1, 5, 9};
7
8  // Sorting using std::sort
9  std::sort(numbers.begin(), numbers.end());
10
11  // Printing the sorted vector
12  for (const int& num : numbers) {
13    std::cout << num << " ";
14  }
15}

11 1 3 4 5 9

Using std::stable_sort()

std::stable_sort() is a stable sorting algorithm, meaning it preserves the relative order of equivalent elements.

This stability is useful when the order of equal elements carries semantic meaning, such as when sorting a list of employees by department and then by name.

Here's an example using std::stable_sort():

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct Employee {
6  std::string name;
7  int department;
8
9  bool operator<(const Employee& other) const {
10    return department < other.department;
11  }
12};
13
14int main() {
15  std::vector<Employee> employees{
16    {"Alice", 2},
17    {"Bob", 1},
18    {"Charlie", 2},
19    {"David", 1}
20  };
21
22  // Stable sorting by department
23  std::stable_sort(employees.begin(),
24    employees.end());
25
26  // Printing the sorted employees
27  for (const Employee& emp : employees) {
28    std::cout << emp.name << " (Dept "
29      << emp.department << ")\n";
30  }
31}

1Bob (Dept 1)
2David (Dept 1)
3Alice (Dept 2)
4Charlie (Dept 2)

Key Differences

• Stability: std::sort() is not stable, meaning the relative order of equivalent elements is not guaranteed to be preserved. std::stable_sort(), on the other hand, guarantees that equivalent elements retain their relative order.
• Performance: std::sort() is generally faster than std::stable_sort() due to fewer constraints. It uses an introspective sort algorithm, combining quicksort, heapsort, and insertion sort. std::stable_sort() typically uses a combination of merge sort, which ensures stability but with a slightly higher time complexity and potentially higher memory usage.

When to Use Which

• Use std::sort() when performance is critical and the order of equivalent elements does not matter.
• Use std::stable_sort() when you need to maintain the relative order of equivalent elements.

Understanding the differences between these sorting algorithms helps in choosing the right tool for your specific needs, ensuring both efficiency and correctness in your programs.