Iterator and Range-Based Algorithms

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

What is the difference between std::sort() and std::stable_sort()?

Abstract art representing computer programming

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

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

#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.

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

Free, Unlimited Access

Professional C++

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

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved