Go rant

[Don]

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? 

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.