Re: [boost] Proposed templated integer_sort

From: Johan Råde (rade_at_[hidden])
Date: 2008-06-28 09:57:12

Hi Steven,

If you can provide a generic implementation that can sort

1. integers, floats, strings
2. structs that should be sorted according a data member that is an integer, float or string
3. pointers to structs as in 2

then I would be interested.

--Johan Råde

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.  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
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>