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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk