Go rant

[justme]

Denis Koroskin Wrote:

> On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme at somewhere.net> wrote:
> 
> > Nekuromento Wrote:
> >
> >> Simen kjaeraas Wrote:
> >>
> >> > Kevin Bealer <kevinbealer at gmail.com> 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? What does myarray.sort  
> > in D use now?
> 
> http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.d

I can't really read that code - apparently the author has not ever read the Clean code book (http://www.amazon.com/Clean-Code-Handbook-Software-Craftsmanship/dp/0132350882). To me it looks like it uses insertion sort for small arrays (< 8 elements) and single-pivot quicksort for larger ones.