28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.2 Nth element [alg.nth.element]

template<class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable. The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.

Effects: After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted, unless nth == last. Also for every iterator i in the range [first, nth) and every iterator j in the range [nth, last) it holds that: !(*j < *i) or comp(*j, *i) == false.

Complexity: For the overloads with no ExecutionPolicy, linear on average. For the overloads with an ExecutionPolicy, $O (N)$ applications of the predicate, and $O (N log N)$ swaps, where $N = last - first$ .