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

["Belov, Eugeny" <Eugeny_Belov at stl dot sarov dot ru>]

   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.
Eugeny.


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 
> itself.
>
> Regards
>  Wolfgang
>
> -------------------------------------------------------------------------
> Wolfgang Bangerth              email:           bangerth@ticam.utexas.edu
>                               www: http://www.ticam.utexas.edu/~bangerth