[boost] Proposed templated integer_sort

From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-06-27 22:39:56

Would there be interest in an integer_sort call that is faster than std::sort?
Spreadsort is an in-place hybrid radix-based and comparison-based algorithm with
better worst-case and average-case (roughly 20-50%) performance than introsort 
on random integer data. 
The worst-case advantage is algorithmic, with Spreadsort taking the better of
O(n(square_root(bit_sizeof(data) - log(n)))) and O(nlog(n)) time.  
For 32-bit integers, that's O(n(square_root(32 - log(n)))), 
so for a log(n) of 16 (65536 items), it's 4n (plus a small constant times n),
vs 16n for introsort.
For larger n, the advantage vs. pure comparison-based algorithms increases.
In effect, Spreadsort smoothly transitions from pure MSB Radix sort to std::sort 
with its data cut up by a couple iterations of MSB Radix sort
(reducing the size of the log(n) factor),
depending upon the distribution and size of the data.

I could write a templated version of Spreadsort for the Boost library if there
is interest.  It would work for anything that supports the << and - operators.
It could also handle standard floats sorted as integers.
Functors supporting << and - could make it more general.
Multi-dimensional sorting is also sped up by Spreadsort.
I could also write a similar string_sort, that should also be significantly 
faster than std::sort.  This would look much like postal sort, just using
introsort after a certain number of iterations.
Is this of interest?

http://sourceforge.net/projects/spreadsort