Skip to content
Tutorials Center
My learning

Topics

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.

C++
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

C++ Ascending, descending and custom order

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++ Sorting structs, ranges::sort and projections

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++
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 with sort, break ties yourself as the example does.
  • Comparator rules. comp(a, a) must be false, and if comp(a, b) and comp(b, c) then comp(a, c). Writing a <= b breaks 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::list does not compile with std::sort; call list.sort(). For forward_list call forward_list::sort().
  • Sort once, search many times. After sorting, use binary_search, lower_bound and equal_range for 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_sort or nth_element does 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_sorted is a cheap sanity check in tests and assertions.
  • Moving elements. sort moves 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.