Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards


Function template integer_sort

boost::sort::spreadsort::integer_sort — Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. (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 RandomAccessIter, typename Right_shift, typename Compare> 
  void integer_sort(RandomAccessIter first, RandomAccessIter last, 
                    Right_shift shift, Compare comp);


integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than std::sort for large tests (>=100kB).
Worst-case performance is O(N * (lg(range)/s + s)) , so integer_sort is asymptotically faster than pure comparison-based algorithms. s is max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is O(N * ((32/11) slow radix-based iterations fast comparison-based iterations).

Some performance plots of runtime vs. n and log(range) are provided:

[Warning] 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] Warning

Invalid arguments cause undefined behaviour.

[Note] Note

spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.

The lesser of O(N*log(N)) comparisons and O(N*log(K/S + S)) operations worst-case, where:

* N is last - first,

* K is the log of the range in bits (32 for 32-bit 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).



A binary functor that returns whether the first element passed to it should go before the second in order.


Iterator pointer to first element.


Iterator pointing to one beyond the end of data.


Functor that returns the result of shifting the value_type right a specified number of bits.


[first, last) is a valid range.


RandomAccessIter value_type is mutable.


The elements in the range [first, last) are sorted in ascending order.




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