Re: [boost] Proposed templated integer_sort

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-28 21:27:02

Steven Ross wrote:
> 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.  

The world needs more generic algorithms, so I'm interested purely on
that basis.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com