• justme <justme somewhere.net> Dec 29 2009

justme <justme somewhere.net> writes:

Denis Koroskin Wrote:

 On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme somewhere.net> wrote:
 
 Nekuromento Wrote:

 Simen kjaeraas Wrote:

 Kevin Bealer <kevinbealer gmail.com> wrote:

 I'm curious if the multi-pivot quicksort (I think everyone gets  




 mean by this?  Divide by more than one pivot on each pass?  I can  




 details if you like ...) has been tried out much.  It seems like it  




 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-Craftsman
hip/dp/0132350882). To me it looks like it uses insertion sort for small arrays
(< 8 elements) and single-pivot quicksort for larger ones.