Iterator and Range-Based Algorithms

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

## What is the 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():

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
std::vector<int> numbers{3, 1, 4, 1, 5, 9};

// Sorting using std::sort
std::sort(numbers.begin(), numbers.end());

// Printing the sorted vector
for (const int& num : numbers) {
std::cout << num << " ";
}
}
1 1 3 4 5 9

### Usingstd::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():

#include <algorithm>
#include <iostream>
#include <vector>

struct Employee {
std::string name;
int department;

bool operator<(const Employee& other) const {
return department < other.department;
}
};

int main() {
std::vector<Employee> employees{
{"Alice", 2},
{"Bob", 1},
{"Charlie", 2},
{"David", 1}
};

// Stable sorting by department
std::stable_sort(employees.begin(),
employees.end());

// Printing the sorted employees
for (const Employee& emp : employees) {
std::cout << emp.name << " (Dept "
<< emp.department << ")\n";
}
}
Bob (Dept 1)
David (Dept 1)
Alice (Dept 2)
Charlie (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.

This Question is from the Lesson:

### Iterator and Range-Based Algorithms

An introduction to iterator and range-based algorithms, using examples from the standard library

Answers to questions are automatically generated and may not have been reviewed.

This Question is from the Lesson:

### Iterator and Range-Based Algorithms

An introduction to iterator and range-based algorithms, using examples from the standard library

Part of the course:

## Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

### This course includes:

• 124 Lessons
• 550+ Code Samples
• 96% Positive Reviews
• Regularly Updated
• Help and FAQ
Free, Unlimited Access

### Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.