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<http://goanna.cs.rmit.edu.au/%7Ejz/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@method-solutions.com > 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.