#include <algorithm>
  void nth_element( iterator start, iterator middle, iterator end );
  void nth_element( iterator start, iterator middle, iterator end, StrictWeakOrdering cmp );

The nth_element() function semi-sorts the range of elements defined by [start,end). It puts the element that middle points to in the place that it would be 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.