Nth element

nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)	Function
nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp)	Function

template 
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last);

template 
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last, Compare comp);

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. Also for any iterator i in the range [first, nth) and any iterator j in the range [nth, last) it holds that !(*i > *j) or comp(*i, *j) == false. It is linear on the average.