Function template integer_sort

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, < detail::min_sort_size).

Synopsis

// In header: <boost/sort/spreadsort/integer_sort.hpp>


template<typename Range, typename Right_shift> 
  void integer_sort(Range & range, Right_shift shift);

Description

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. 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:
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. Invalid arguments cause undefined behaviour.

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.

Invalid arguments cause undefined behaviour.

	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).

Parameters:

`range`	Range [first, last) for sorting.
`shift`	A functor that returns the result of shifting the value_type right a specified number of bits.

Requires:

[first, last) is a valid range.

Postconditions:

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

Throws:

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.

Boost C++ Libraries