Re: [boost] Sorting

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-07-23 13:00:51

>> Anyone know if this is truly a novel algorithm?
>> This implementation is GPL'ed which makes it pretty useless to me.
>> If it really is good perhaps someone could provide a Boost
implementation.
>>
>> Thanks,
>>
>> Michael Marcin
>>
>>
>>
>>
>I began the sorting library, and one of the functions in  the library,
multikey quicksort, is very >good for sorting arrrays of strings and
probably has better worst and best case time than >burstsort time if it is
true that burstsort is an MSD radix sort. This is because multikey
>quicksort is a variation of MSD radix sort that does not waste time on
empty buckets, unlike >traditional MSD radix sort. See Algorithms in C++,
third edition, for a much more detailed >explanation of multikey quicksort
(in the book it is called three way radix quicksort). Also, I >have improved
the library, and will post new code as soon as possible.
I take back what I said. I tested the code and found that burstsort is
faster. I will try to modify burstsort to work for arrays of any type.
However, those modifications may slow down burstsort to the point of being
slower than multikey quicksort.