Syntax:

    #include <algorithm>
    void nth_element( random_access_iterator start, random_access_iterator nth, random_access_iterator end );
    void nth_element( random_access_iterator start, random_access_iterator nth, random_access_iterator end, StrictWeakOrdering cmp );

The nth_element() function semi-sorts the range of elements defined by [start,end). It puts the element of the range to the nth position, that would be there, if the entire range was sorted, and it makes sure that none of the elements before that element are greater than any of the elements that come after that element.

nth_element() runs in linear time on average.

Related Topics: partial_sort