nth_element()

nth_element() reorders the sequence so that all elements less than the nth element occur before it and all elements that are greater occur after it. For example, given

int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 }; 

an invocation of nth_element() marking ia+6 as nth (it has a value of 26)

nth_element( ia, ia+6, &ia[12] ); 

yields a sequence in which the seven elements less than 26 are to its left, and the four elements greater than 26 are to its right:

{ 23,20,22,17,15,19,12,26,51,35,40,29 } 

The elements on either side of the nth element are not guaranteed to be in any particular order. An optional fourth parameter allows us to indicate a comparison other than the default less-than operator.