Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

C++ std::stable_sort and std::partial_sort

Reference for std::stable_sort, partial_sort, partial_sort_copy and is_sorted: keeping equal elements in order, finding the top k items, and their complexity.

std::sort is not the only sorting algorithm in <algorithm>. Two variations cover situations where it is the wrong tool.

std::stable_sort sorts like std::sort but guarantees that elements that compare equal keep their original relative order. That matters when you sort the same data twice by different keys (for example by city, then by name) or when the order of ties is visible to the user. std::partial_sort puts only the smallest k elements, in order, at the front of the range and leaves the rest in an unspecified order. It does less work than a full sort when you only need a "top 10" list.

C++
std::stable_sort(v.begin(), v.end(), by_age);        // ties keep input order
std::partial_sort(v.begin(), v.begin() + 3, v.end()); // 3 smallest, sorted

Try it

C++ Stable versus not stable: two-key sorting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Top k with partial_sort and partial_sort_copy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
void std::stable_sort(RandomIt first, RandomIt last);
void std::stable_sort(RandomIt first, RandomIt last, Compare comp);

void std::partial_sort(RandomIt first, RandomIt middle, RandomIt last);
void std::partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);

RandomIt std::partial_sort_copy(InputIt first, InputIt last,
                                RandomIt d_first, RandomIt d_last, [Compare comp]);

bool     std::is_sorted(It first, It last, [Compare comp]);
It       std::is_sorted_until(It first, It last, [Compare comp]);
// C++20: std::ranges::stable_sort, partial_sort, partial_sort_copy, is_sorted
Name Description
first, last The range to process.
middle For partial_sort: the end of the sorted prefix. The middle - first smallest elements are sorted into [first, middle).
d_first, d_last For partial_sort_copy: the destination range; its size decides how many elements are copied.
comp Strict weak ordering, comp(a, b) is true if a goes before b. Default operator<.

Returns: stable_sort and partial_sort return void. partial_sort_copy returns an iterator to the end of the copied elements in the destination. is_sorted returns a bool and is_sorted_until returns the first iterator where the order breaks (or last).

Usage notes

  • stable_sort complexity. O(n log n) comparisons when it can allocate a temporary buffer (O(n log^2 n) otherwise), and it uses O(n) extra memory. It is often a little slower than sort; use it only when stability matters.
  • partial_sort complexity. About O(n log k) comparisons, where k = middle - first. It builds a heap of the first k elements and replaces the largest with smaller ones it finds. For small k it is much faster than sorting everything.
  • The tail is unspecified. After partial_sort, elements in [middle, last) are present but in no useful order. Do not read meaning into them.
  • Need only the k-th value, not a sorted prefix? std::nth_element is O(n) on average.
  • Multi-key sorts. A stable sort on the least important key first, then the most important last, builds a lexicographic order. You can also compare both keys in one comparator (std::tie(a.city, a.name) < std::tie(b.city, b.name)) with a plain sort.
  • Sorting stability for lists. std::list::sort and std::forward_list::sort are stable, which std::sort is not.
  • Sort order of equal elements in sort is implementation-defined and can differ between compilers and versions: never write tests that depend on it.
  • is_sorted is linear and useful in assertions. Remember to pass the same comparator you sorted with.