libstdc++/8195: n-th algorithm (STL) doesn`t work properly

Belov, Eugeny
Fri Oct 11 08:42:00 GMT 2002

    Hello Wolfgang

  I am understanding that the principle of this algorithm (in simple 
terms) is to divide the sequence into 2 parts like this:
smaller elements , n-th element, bigger elements,  and in the general 
case both parts can be unsorted.
  But the real problem in this case is that smaller elements comes after 
n-th ("n-th" is the integer with value 12 - the biggiest of all other 
elements), i.e. the sequence after using the nth_element() is "4 4 5 6 6 
6 9 _12_ 8 10" and in this case I think the n-th algorithm 
implementation make a mistake.

With best regards.

Wolfgang Bangerth wrote:

>This is not a bug, so may be closed.
>nth_element does not sort the _entire_ array, it only makes sure that the 
>elements before the nth-pointer are smaller, and the ones behind that are 
>larger than the element pointed to by nth (the second argument). It makes 
>no guarantees that each of these two parts of the entire range is sorted 
>  Wolfgang
>Wolfgang Bangerth              email: 
>                               www:

More information about the Gcc-bugs mailing list