Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

The C++ std::nth_element algorithm

Reference for std::nth_element: partially order a range so the element at position n is where it would be if sorted, with examples for median and top-k.

std::nth_element (header <algorithm>) solves the selection problem: it rearranges a range so that the element at position nth is exactly the one that would be there if the whole range were sorted. Everything before nth is not greater than it, everything after is not less. The two sides are not sorted themselves.

Because it does not sort, it runs in linear time on average (O(n)) instead of O(n log n). That makes it the right tool for the median, percentiles, "the k-th smallest" and "the top k in any order". It needs random-access iterators and modifies the range.

C++
std::nth_element(v.begin(), v.begin() + k, v.end());
// v[k] is now the (k+1)-th smallest value

Try it

C++ Median and k-th smallest

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 in any order, then sort only those

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::nth_element(RandomIt first, RandomIt nth, RandomIt last);
void std::nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);
void std::nth_element(ExecPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last);   // C++17

// C++20
std::ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
Name Description
first, last The range to rearrange.
nth The position that will hold the value it would have in sorted order. Must be in [first, last].
comp Strict weak ordering. Default is operator<.

Returns: void (the ranges version returns an iterator equal to last).

After the call: for every iterator i in [first, nth) and j in [nth, last), comp(*j, *i) is false, so no element on the right is "before" an element on the left. If nth == last, nothing is guaranteed and nothing needs to be done.

Usage notes

  • Complexity. Linear on average, O(n). Typically implemented with introselect (quickselect with a fallback), which gives worst-case O(n log n) in libstdc++ but the standard only requires linear on average.
  • Neither side is sorted. Print or search the sides only after sorting them. Do not use binary_search on the result.
  • Order of equal elements and the arrangement on each side are unspecified and implementation dependent.
  • Median of an even count needs the two middle elements. After nth_element at the lower middle, the upper middle is the minimum of the right part, found with min_element, as in the example.
  • For top-k with sorted output combine nth_element with a sort of the first k elements, which is O(n + k log k), or use partial_sort, O(n log k).
  • It modifies the input. Copy the data first when the original order matters.
  • Floating point. Do not use with NaN values: < is not a strict weak ordering for them and the result is undefined.
  • Random access only. Lists, sets and other non-random-access containers cannot be used.
  • Selection by percentile. For the p-th percentile compute an index k = (n - 1) * p / 100 and call nth_element at that index; interpolate between neighbors if you need exact statistical definitions.