1 //Templated Spreadsort-based implementation of integer_sort
3 // Copyright Steven J. Ross 2001 - 2014.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
8 // See http://www.boost.org/libs/sort/ for library home page.
11 Some improvements suggested by:
12 Phil Endecott and Frank Gennari
14 Doxygen comments by Paul A. Bristow Jan 2015
18 #ifndef BOOST_INTEGER_SORT_HPP
19 #define BOOST_INTEGER_SORT_HPP
24 #include <boost/static_assert.hpp>
25 #include <boost/sort/spreadsort/detail/constants.hpp>
26 #include <boost/sort/spreadsort/detail/integer_sort.hpp>
30 namespace spreadsort {
31 //Top-level sorting call for integers.
34 /*! \brief Integer sort algorithm using random access iterators.
35 (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
37 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
38 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
39 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
40 so @c integer_sort is asymptotically faster
41 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
42 so its worst-case with default settings for 32-bit integers is
43 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
44 Some performance plots of runtime vs. n and log(range) are provided:\n
45 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
47 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
49 \param[in] first Iterator pointer to first element.
50 \param[in] last Iterator pointing to one beyond the end of data.
52 \pre [@c first, @c last) is a valid range.
53 \pre @c RandomAccessIter @c value_type is mutable.
54 \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
55 \pre @c RandomAccessIter @c value_type supports the @c operator>>,
56 which returns an integer-type right-shifted a specified number of bits.
57 \post The elements in the range [@c first, @c last) are sorted in ascending order.
59 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
60 the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.
62 \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.
63 \warning Invalid arguments cause undefined behaviour.
64 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
65 enabling faster generic-programming.
67 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
68 \remark * N is @c last - @c first,
69 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
70 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
73 template <class RandomAccessIter>
74 inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
76 // Don't sort if it's too small to optimize.
77 if (last - first < detail::min_sort_size)
78 std::sort(first, last);
80 detail::integer_sort(first, last, *first >> 0);
83 /*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
84 (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
86 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
87 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
88 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
89 so @c integer_sort is asymptotically faster
90 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
91 so its worst-case with default settings for 32-bit integers is
92 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
93 Some performance plots of runtime vs. n and log(range) are provided:\n
94 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
96 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
98 \param[in] first Iterator pointer to first element.
99 \param[in] last Iterator pointing to one beyond the end of data.
100 \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits.
101 \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
103 \pre [@c first, @c last) is a valid range.
104 \pre @c RandomAccessIter @c value_type is mutable.
105 \post The elements in the range [@c first, @c last) are sorted in ascending order.
109 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
110 the right shift, subtraction of right-shifted elements, functors,
111 or any operations on iterators throw.
113 \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.
114 \warning Invalid arguments cause undefined behaviour.
115 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
116 enabling faster generic-programming.
118 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
119 \remark * N is @c last - @c first,
120 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
121 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
123 template <class RandomAccessIter, class Right_shift, class Compare>
124 inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
125 Right_shift shift, Compare comp) {
126 if (last - first < detail::min_sort_size)
127 std::sort(first, last, comp);
129 detail::integer_sort(first, last, shift(*first, 0), shift, comp);
132 /*! \brief Integer sort algorithm using random access iterators with just right-shift functor.
133 (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
135 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
136 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
139 Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
140 so @c integer_sort is asymptotically faster
141 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
142 so its worst-case with default settings for 32-bit integers is
143 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
144 Some performance plots of runtime vs. n and log(range) are provided:\n
145 * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n
146 * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
148 \param[in] first Iterator pointer to first element.
149 \param[in] last Iterator pointing to one beyond the end of data.
150 \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits.
152 \pre [@c first, @c last) is a valid range.
153 \pre @c RandomAccessIter @c value_type is mutable.
154 \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
155 \post The elements in the range [@c first, @c last) are sorted in ascending order.
157 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
158 the right shift, subtraction of right-shifted elements, functors,
159 or any operations on iterators throw.
161 \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.
162 \warning Invalid arguments cause undefined behaviour.
163 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
164 enabling faster generic-programming.
166 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
167 \remark * N is @c last - @c first,
168 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
169 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
172 template <class RandomAccessIter, class Right_shift>
173 inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
175 if (last - first < detail::min_sort_size)
176 std::sort(first, last);
178 detail::integer_sort(first, last, shift(*first, 0), shift);