Denis Koroskin wrote:
On Tue, 29 Dec 2009 21:36:25 +0300, justme <[email protected]> wrote:
Nekuromento Wrote:
Simen kjaeraas Wrote:
> Kevin Bealer <[email protected]> wrote:
>
> > I'm curious if the multi-pivot quicksort (I think everyone gets
what I
> > mean by this? Divide by more than one pivot on each pass? I can
give
> > details if you like ...) has been tried out much. It seems like
it must
> > have been, but it also seems like something that would have
> > cache-awareness advantages that would not show up in the simplified
> > comparison-counting way of thinking about efficiency.
>
> I've heard of two-pivot quicksort, but can't remember where.
>
> --
> Simen
Some information about dual pivot quicksort:
http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
Looks awesome? But the proof is too academical for my taste. Why can't
D implement a three-pivot quicksort and beat Java?
Yeah, that's the obvious question -- what's the optimum number of
pivots? It's a bit annoying that that paper doesn't mention it.
