...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::sort::spreadsort::integer_sort — Integer sort algorithm using range. (All variants fall back to boost::sort::pdqsort
if the data size is too small, < detail::min_sort_size
).
// In header: <boost/sort/spreadsort/integer_sort.hpp> template<typename Range> void integer_sort(Range & range);
integer_sort
is a fast templated inplace hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than std::sort
for large tests (>=100kB).
Worstcase performance is O(N * (lg(range)/s + s)) , so integer_sort
is asymptotically faster than pure comparisonbased algorithms. s
is max_splits
, which defaults to 11, so its worstcase with default settings for 32bit integers is O(N * ((32/11) slow radixbased iterations fast comparisonbased iterations).
Some performance plots of runtime vs. n and log(range) are provided:
windows_integer_sort
osx_integer_sort
Warning  

Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. 
Warning  

Invalid arguments cause undefined behaviour. 
Note  


The lesser of O(N*log(N)) comparisons and O(N*log(K/S + S)) operations worstcase, where:
* N is last
 first
,
* K is the log of the range in bits (32 for 32bit integers using their full range),
* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
Parameters: 


Requires: 
[ 

Postconditions: 
The elements in the range [ 

Throws: 
std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of rightshifted elements, functors, or any operations on iterators throw. 