1//Templated Spreadsort-based implementation of integer_sort
2
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)
7
8// See http://www.boost.org/libs/sort/ for library home page.
9
10/*
11Some improvements suggested by:
12Phil Endecott and Frank Gennari
13
14Doxygen comments by Paul A. Bristow Jan 2015
15
16*/
17
18#ifndef BOOST_INTEGER_SORT_HPP
19#define BOOST_INTEGER_SORT_HPP
20#include <algorithm>
21#include <vector>
22#include <cstring>
23#include <limits>
24#include <boost/static_assert.hpp>
25#include <boost/sort/spreadsort/detail/constants.hpp>
26#include <boost/sort/spreadsort/detail/integer_sort.hpp>
27#include <boost/range/begin.hpp>
28#include <boost/range/end.hpp>
29
30namespace boost {
31namespace sort {
32namespace spreadsort {
33 //Top-level sorting call for integers.
34
35
36/*! \brief Integer sort algorithm using random access iterators.
37 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size).
38
39 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
40which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
41Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
42so @c integer_sort is asymptotically faster
43than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
44so its worst-case with default settings for 32-bit integers is
45<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
46Some performance plots of runtime vs. n and log(range) are provided:\n
47 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
48 \n
49 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
50
51 \param[in] first Iterator pointer to first element.
52 \param[in] last Iterator pointing to one beyond the end of data.
53
54 \pre [@c first, @c last) is a valid range.
55 \pre @c RandomAccessIter @c value_type is mutable.
56 \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
57 \pre @c RandomAccessIter @c value_type supports the @c operator>>,
58 which returns an integer-type right-shifted a specified number of bits.
59 \post The elements in the range [@c first, @c last) are sorted in ascending order.
60
61 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
62 the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.
63
64 \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.
65 \warning Invalid arguments cause undefined behaviour.
66 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
67 enabling faster generic-programming.
68
69 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
70 \remark * N is @c last - @c first,
71 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
72 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
73
74*/
75 template <class RandomAccessIter>
76 inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
77 {
78 // Don't sort if it's too small to optimize.
79 if (last - first < detail::min_sort_size)
80 boost::sort::pdqsort(first, last);
81 else
82 detail::integer_sort(first, last, *first >> 0);
83 }
84
85/*! \brief Integer sort algorithm using range.
86 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size).
87
88 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
89which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
90Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
91so @c integer_sort is asymptotically faster
92than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
93so its worst-case with default settings for 32-bit integers is
94<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
95Some performance plots of runtime vs. n and log(range) are provided:\n
96 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
97 \n
98 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
99
100 \param[in] range Range [first, last) for sorting.
101
102 \pre [@c first, @c last) is a valid range.
103 \post The elements in the range [@c first, @c last) are sorted in ascending order.
104
105 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
106 the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.
107
108 \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.
109 \warning Invalid arguments cause undefined behaviour.
110 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
111 enabling faster generic-programming.
112
113 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
114 \remark * N is @c last - @c first,
115 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
116 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
117
118*/
119template <class Range>
120inline void integer_sort(Range& range)
121{
122 integer_sort(boost::begin(range), boost::end(range));
123}
124
125/*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
126 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size).
127
128 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
129which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
130Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
131so @c integer_sort is asymptotically faster
132than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
133so its worst-case with default settings for 32-bit integers is
134<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
135Some performance plots of runtime vs. n and log(range) are provided:\n
136 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
137 \n
138 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
139
140 \param[in] first Iterator pointer to first element.
141 \param[in] last Iterator pointing to one beyond the end of data.
142 \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits.
143 \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
144
145 \pre [@c first, @c last) is a valid range.
146 \pre @c RandomAccessIter @c value_type is mutable.
147 \post The elements in the range [@c first, @c last) are sorted in ascending order.
148
149 \return @c void.
150
151 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
152 the right shift, subtraction of right-shifted elements, functors,
153 or any operations on iterators throw.
154
155 \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.
156 \warning Invalid arguments cause undefined behaviour.
157 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
158 enabling faster generic-programming.
159
160 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
161 \remark * N is @c last - @c first,
162 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
163 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
164*/
165 template <class RandomAccessIter, class Right_shift, class Compare>
166 inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
167 Right_shift shift, Compare comp) {
168 if (last - first < detail::min_sort_size)
169 boost::sort::pdqsort(first, last, comp);
170 else
171 detail::integer_sort(first, last, shift(*first, 0), shift, comp);
172 }
173
174/*! \brief Integer sort algorithm using range with both right-shift and user-defined comparison operator.
175 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size).
176
177 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
178which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
179Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
180so @c integer_sort is asymptotically faster
181than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
182so its worst-case with default settings for 32-bit integers is
183<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
184Some performance plots of runtime vs. n and log(range) are provided:\n
185 <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
186 \n
187 <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
188
189 \param[in] range Range [first, last) for sorting.
190 \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits.
191 \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
192
193 \pre [@c first, @c last) is a valid range.
194 \post The elements in the range [@c first, @c last) are sorted in ascending order.
195
196 \return @c void.
197
198 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
199 the right shift, subtraction of right-shifted elements, functors,
200 or any operations on iterators throw.
201
202 \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.
203 \warning Invalid arguments cause undefined behaviour.
204 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
205 enabling faster generic-programming.
206
207 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
208 \remark * N is @c last - @c first,
209 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
210 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
211*/
212template <class Range, class Right_shift, class Compare>
213inline void integer_sort(Range& range, Right_shift shift, Compare comp)
214{
215 integer_sort(boost::begin(range), boost::end(range), shift, comp);
216}
217
218/*! \brief Integer sort algorithm using random access iterators with just right-shift functor.
219 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size).
220
221 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
222which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
223
224\par Performance:
225Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
226so @c integer_sort is asymptotically faster
227than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
228so its worst-case with default settings for 32-bit integers is
229<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
230Some performance plots of runtime vs. n and log(range) are provided:\n
231 * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n
232 * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
233
234 \param[in] first Iterator pointer to first element.
235 \param[in] last Iterator pointing to one beyond the end of data.
236 \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits.
237
238 \pre [@c first, @c last) is a valid range.
239 \pre @c RandomAccessIter @c value_type is mutable.
240 \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
241 \post The elements in the range [@c first, @c last) are sorted in ascending order.
242
243 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
244 the right shift, subtraction of right-shifted elements, functors,
245 or any operations on iterators throw.
246
247 \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.
248 \warning Invalid arguments cause undefined behaviour.
249 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
250 enabling faster generic-programming.
251
252 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
253 \remark * N is @c last - @c first,
254 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
255 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
256
257*/
258 template <class RandomAccessIter, class Right_shift>
259 inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
260 Right_shift shift) {
261 if (last - first < detail::min_sort_size)
262 boost::sort::pdqsort(first, last);
263 else
264 detail::integer_sort(first, last, shift(*first, 0), shift);
265 }
266
267
268/*! \brief Integer sort algorithm using range with just right-shift functor.
269 (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size).
270
271 \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
272which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
273
274\par Performance:
275Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
276so @c integer_sort is asymptotically faster
277than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
278so its worst-case with default settings for 32-bit integers is
279<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
280Some performance plots of runtime vs. n and log(range) are provided:\n
281 * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n
282 * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
283
284 \param[in] range Range [first, last) for sorting.
285 \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits.
286
287 \pre [@c first, @c last) is a valid range.
288 \post The elements in the range [@c first, @c last) are sorted in ascending order.
289
290 \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
291 the right shift, subtraction of right-shifted elements, functors,
292 or any operations on iterators throw.
293
294 \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.
295 \warning Invalid arguments cause undefined behaviour.
296 \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
297 enabling faster generic-programming.
298
299 \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
300 \remark * N is @c last - @c first,
301 \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
302 \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
303
304*/
305template <class Range, class Right_shift>
306inline void integer_sort(Range& range, Right_shift shift)
307{
308 integer_sort(boost::begin(range), boost::end(range), shift);
309}
310}
311}
312}
313
314#endif
315
316

source code of boost/libs/sort/include/boost/sort/spreadsort/integer_sort.hpp