
Boost : 
From: Steven Ross (spreadsort_at_[hidden])
Date: 20080627 22:39:56
Would there be interest in an integer_sort call that is faster than std::sort?
Spreadsort is an inplace hybrid radixbased and comparisonbased algorithm with
better worstcase and averagecase (roughly 2050%) performance than introsort
on random integer data.
The worstcase advantage is algorithmic, with Spreadsort taking the better of
O(n(square_root(bit_sizeof(data)  log(n)))) and O(nlog(n)) time.
For 32bit 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 comparisonbased 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.
Multidimensional 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk