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

This is the documentation for an old version of boost. Click here for the latest Boost documentation.

Function template string_sort

boost::sort::spreadsort::string_sort — String sort algorithm using random access iterators, allowing character-type overloads.
(All variants fall back to std::sort if the data size is too small, < detail::min_sort_size).


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

template<typename RandomAccessIter, typename Unsigned_char_type> 
  void string_sort(RandomAccessIter first, RandomAccessIter last, 
                   Unsigned_char_type unused);


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



Iterator pointer to first element.


Iterator pointing to one beyond the end of data.


value with the same type as the result of the [] operator, defining the Unsigned_char_type. The actual value is unused.

Template Parameters:


Random access iterator


Unsigned character type used for string.


[first, last) is a valid range.


RandomAccessIter value_type is mutable.


RandomAccessIter value_type is LessThanComparable


RandomAccessIter value_type supports the operator>>, which returns an integer-type right-shifted a specified number of bits.


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.