Daily bit(e) of C++ | std::nth_element
Daily bit(e) of C++ ♻️40, The linear complexity algorithm that partitions a range around a pivot position that will contain the "as-if-sorted" element: std::nth_element.
The std::nth_element is a partitioning algorithm with linear complexity that reorders the elements of the given range so that the element under the pivot iterator is the element that would be there if the range were sorted.
This can be useful for picking the various percentiles out of range (such as the median) without explicitly sorting it (which would be an O(n*logn) operation).
The algorithm's linear complexity comes with a non-trivial constant cost, which means that if you are looking for an extreme percentile, the std::partial_sort algorithm can be faster.
The algorithm provides both a C++17 parallel and C++20 range version.
