Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-01-08 02:51:18

I've finished optimizing and testing Spreadsort
(integer_sort/float_sort/string_sort), a hybrid radix-based/comparison-based
algorithm.  It is now available from:
http://sourceforge.net/projects/spreadsort
I have tested it using an (included) automated test script on Mac OSX and
Cygwin with a range of different distributions of random data on 20MB data
sets.  It is roughly twice as fast as std::sort on average across all three
data types and many distributions, with the main exception of a 28X average
performance improvement for float_sort on Cygwin.  Average runtime seems to
be proportional to roughly theta(n*square_root(log(n))); worst-case is more
complicated but better than O(nlog(n)), due to the radix-based portion.
Test it and see for yourself how it performs on your system.
At this point I'm looking for suggestions on formatting it to submit as a
Boost.Algorithm.Sorting namespace.  I would appreciate comments that aid
that process.  I am also interested in knowing whether people would like a
parallel_sort integrated in Boost.Algorithm.Sorting with Spreadsort.