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.
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
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.
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
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_sortcomplexity. 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 thansort; use it only when stability matters.partial_sortcomplexity. About O(n log k) comparisons, wherek = middle - first. It builds a heap of the firstkelements and replaces the largest with smaller ones it finds. For smallkit 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_elementis 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 plainsort. - Sorting stability for lists.
std::list::sortandstd::forward_list::sortare stable, whichstd::sortis not. - Sort order of equal elements in
sortis implementation-defined and can differ between compilers and versions: never write tests that depend on it. is_sortedis linear and useful in assertions. Remember to pass the same comparator you sorted with.