...one of the most highly
regarded and expertly designed C++ library projects in the
world. — Herb Sutter and Andrei
boost::sort::spreadsort::integer_sort — Integer sort algorithm using range with just right-shift functor. (All variants fall back to
boost::sort::pdqsort if the data size is too small, <
// In header: <boost/sort/spreadsort/integer_sort.hpp> template<typename Range, typename Right_shift> void integer_sort(Range & range, Right_shift shift);
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).
Performance: Worst-case performance is O(N * (lg(range)/s + s)) , so
integer_sort is asymptotically faster than pure comparison-based algorithms.
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:
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.
Invalid arguments cause undefined behaviour.
The lesser of O(N*log(N)) comparisons and O(N*log(K/S + S)) operations worst-case, where:
* N is
* 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).
The elements in the range [
|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.|