Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

Vadim Ponomarenko vadim123 at
Fri Sep 11 23:17:33 UTC 2009

> Vadim-It would be very interesting if something along these lines could be
 made practical.  It isn't obvious how to do step (3) in place.  Either you
 end up allocating extra storage to do it, in which case you might as well
 have used a merge sort, or you end up doing some extra shuffling around 
of the data, in which case it is probably more expensive than the 
dual-partition version.  Perhaps there is some technique I'm not 
thinking of.Cheers,Neal

I didn't think of space requirements, but naively it seems to me that the
 two-pivot method of categorizing the non-pivot elements in place (which
 admittedly I don't entirely understand) would work just as well with the
 m-pivot method.  

More information about the core-libs-dev mailing list