[boost] boost [sorting]

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-07-15 00:12:02

On Mon, 11 Jun 2007, Jake Voytko wrote
>In a paper(http://goanna.cs.rmit.edu.au/~jz/fulltext/acsc03sz.pdf
<http://goanna.cs.rmit.edu.au/%7Ejz/fulltext/acsc03sz.pdf>), the
>creators say that it is essentially a most-significant-digit radix sort,
but
>that the implementation of the radix-sort is based on a "burst trie" (
>http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf
>)

instead of a tree.
>As far as novelty goes I'm not going to make a call, but the sorting method
>itself is old, and the data structure it sits on is designed to quickly
>process strings.
>
>Jake
>
>On 6/11/07, Michael Marcin <mmarcin_at_[hidden] > wrote:
>> A while ago there was talk of a sorting library on this list.
>>
>> I just ran across:
>>
>> http://sourceforge.net/projects/burstsort/
>>
>> 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.