C++ Reference ยท Algorithms
The C++ std::sort algorithm
Reference for std::sort and std::ranges::sort: sorting ranges with operator< or a custom comparator, projections, complexity, stability and common mistakes.
std::sort (header <algorithm>) rearranges the elements of a range into ascending order. By default it compares elements with operator<; you can pass your own comparison function to sort in descending order, by a member of a struct, case-insensitively, or by any rule you can write as "does a come before b?".
It is an in-place, comparison-based sort with average and worst-case complexity of O(n log n) comparisons (typically a hybrid of quicksort, heapsort and insertion sort called introsort). It is not stable: equal elements may end up in a different relative order. It needs random-access iterators, so it works on vector, deque, array, plain arrays and string, but not on std::list (use list::sort) or forward_list.
std::vector<int> v{4, 1, 3}; std::sort(v.begin(), v.end()); // 1 3 4 std::sort(v.begin(), v.end(), std::greater<>{}); // 4 3 1 std::ranges::sort(v); // C++20
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
template<class RandomIt> void std::sort(RandomIt first, RandomIt last); template<class RandomIt, class Compare> void std::sort(RandomIt first, RandomIt last, Compare comp); template<class ExecPolicy, class RandomIt> void std::sort(ExecPolicy&& policy, RandomIt first, RandomIt last); // C++17 // C++20 std::ranges::sort(R&& r, Comp comp = {}, Proj proj = {}); std::ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
| Name | Description |
|---|---|
first, last |
The half-open range [first, last) to sort. |
comp |
A function object where comp(a, b) returns true if a must come before b. Must be a strict weak ordering. Default is operator< (std::less<>). |
proj |
Ranges only: a projection applied to each element before comparing (a member pointer or lambda). |
policy |
An execution policy such as std::execution::par. |
Returns: void for std::sort; the ranges version returns an iterator one past the last element.
Undefined behavior: a comparator that is not a strict weak ordering (using <= or comparing floating point values that include NaN) can crash the program or read out of bounds, not just misorder the output.
Usage notes
- Complexity. O(n log n) comparisons in the worst case since C++11; extra space is O(log n) for the recursion. Fast in practice because it works in place with good cache behavior.
- Not stable. If elements with equal keys must keep their relative order, use
std::stable_sort. To get deterministic output withsort, break ties yourself as the example does. - Comparator rules.
comp(a, a)must befalse, and ifcomp(a, b)andcomp(b, c)thencomp(a, c). Writinga <= bbreaks the first rule. See Writing comparators. - Pass the comparator by value, make it cheap. Capturing large objects by value in a lambda copies them. Take parameters by
const&. - Sorting a
std::listdoes not compile withstd::sort; calllist.sort(). Forforward_listcallforward_list::sort(). - Sort once, search many times. After sorting, use
binary_search,lower_boundandequal_rangefor O(log n) lookups. - Part of a range. Pass any sub-range:
std::sort(v.begin(), v.begin() + k). To get only the smallest k elements,partial_sortornth_elementdoes less work. - Sorting strings with
<compares by character code, not by dictionary order for the user's language; use a collation-aware comparator for that. - Check the result.
std::is_sortedis a cheap sanity check in tests and assertions. - Moving elements.
sortmoves and swaps elements, so the element type needs to be move-constructible and move-assignable (or copyable). Sorting a vector of large objects is faster with move-friendly types or by sorting indices.