Go rant
Denis Koroskin
2korden at gmail.com
Tue Dec 29 10:36:55 PST 2009
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
More information about the Digitalmars-d
mailing list