boost/sort/spreadsort/integer_sort.hpp
//Templated Spreadsort-based implementation of integer_sort // Copyright Steven J. Ross 2001 - 2014. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // See http://www.boost.org/libs/sort/ for library home page. /* Some improvements suggested by: Phil Endecott and Frank Gennari Doxygen comments by Paul A. Bristow Jan 2015 */ #ifndef BOOST_INTEGER_SORT_HPP #define BOOST_INTEGER_SORT_HPP #include <algorithm> #include <vector> #include <cstring> #include <limits> #include <boost/static_assert.hpp> #include <boost/sort/spreadsort/detail/constants.hpp> #include <boost/sort/spreadsort/detail/integer_sort.hpp> #include <boost/range/begin.hpp> #include <boost/range/end.hpp> namespace boost { namespace sort { namespace spreadsort { //Top-level sorting call for integers. /*! \brief Integer sort algorithm using random access iterators. (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so @c integer_sort is asymptotically faster than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n Some performance plots of runtime vs. n and log(range) are provided:\n <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> \n <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> \param[in] first Iterator pointer to first element. \param[in] last Iterator pointing to one beyond the end of data. \pre [@c first, @c last) is a valid range. \pre @c RandomAccessIter @c value_type is mutable. \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> \pre @c RandomAccessIter @c value_type supports the @c operator>>, which returns an integer-type right-shifted a specified number of bits. \post The elements in the range [@c first, @c 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. \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 Invalid arguments cause undefined behaviour. \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming. \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: \remark * N is @c last - @c first, \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). */ template <class RandomAccessIter> inline void integer_sort(RandomAccessIter first, RandomAccessIter last) { // Don't sort if it's too small to optimize. if (last - first < detail::min_sort_size) boost::sort::pdqsort(first, last); else detail::integer_sort(first, last, *first >> 0); } /*! \brief Integer sort algorithm using range. (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so @c integer_sort is asymptotically faster than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n Some performance plots of runtime vs. n and log(range) are provided:\n <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> \n <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> \param[in] range Range [first, last) for sorting. \pre [@c first, @c last) is a valid range. \post The elements in the range [@c first, @c 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. \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 Invalid arguments cause undefined behaviour. \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming. \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: \remark * N is @c last - @c first, \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). */ template <class Range> inline void integer_sort(Range& range) { integer_sort(boost::begin(range), boost::end(range)); } /*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so @c integer_sort is asymptotically faster than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n Some performance plots of runtime vs. n and log(range) are provided:\n <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> \n <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> \param[in] first Iterator pointer to first element. \param[in] last Iterator pointing to one beyond the end of data. \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits. \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. \pre [@c first, @c last) is a valid range. \pre @c RandomAccessIter @c value_type is mutable. \post The elements in the range [@c first, @c last) are sorted in ascending order. \return @c void. \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. \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 Invalid arguments cause undefined behaviour. \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming. \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: \remark * N is @c last - @c first, \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). */ template <class RandomAccessIter, class Right_shift, class Compare> inline void integer_sort(RandomAccessIter first, RandomAccessIter last, Right_shift shift, Compare comp) { if (last - first < detail::min_sort_size) boost::sort::pdqsort(first, last, comp); else detail::integer_sort(first, last, shift(*first, 0), shift, comp); } /*! \brief Integer sort algorithm using range with both right-shift and user-defined comparison operator. (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so @c integer_sort is asymptotically faster than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n Some performance plots of runtime vs. n and log(range) are provided:\n <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> \n <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> \param[in] range Range [first, last) for sorting. \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits. \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. \pre [@c first, @c last) is a valid range. \post The elements in the range [@c first, @c last) are sorted in ascending order. \return @c void. \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. \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 Invalid arguments cause undefined behaviour. \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming. \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: \remark * N is @c last - @c first, \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). */ template <class Range, class Right_shift, class Compare> inline void integer_sort(Range& range, Right_shift shift, Compare comp) { integer_sort(boost::begin(range), boost::end(range), shift, comp); } /*! \brief Integer sort algorithm using random access iterators with just right-shift functor. (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n \par Performance: Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so @c integer_sort is asymptotically faster than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n Some performance plots of runtime vs. n and log(range) are provided:\n * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> \param[in] first Iterator pointer to first element. \param[in] last Iterator pointing to one beyond the end of data. \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits. \pre [@c first, @c last) is a valid range. \pre @c RandomAccessIter @c value_type is mutable. \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> \post The elements in the range [@c first, @c 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. \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 Invalid arguments cause undefined behaviour. \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming. \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: \remark * N is @c last - @c first, \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). */ template <class RandomAccessIter, class Right_shift> inline void integer_sort(RandomAccessIter first, RandomAccessIter last, Right_shift shift) { if (last - first < detail::min_sort_size) boost::sort::pdqsort(first, last); else detail::integer_sort(first, last, shift(*first, 0), shift); } /*! \brief Integer sort algorithm using range with just right-shift functor. (All variants fall back to @c boost::sort::pdqsort if the data size is too small, < @c detail::min_sort_size). \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n \par Performance: Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so @c integer_sort is asymptotically faster than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n Some performance plots of runtime vs. n and log(range) are provided:\n * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> \param[in] range Range [first, last) for sorting. \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits. \pre [@c first, @c last) is a valid range. \post The elements in the range [@c first, @c 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. \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 Invalid arguments cause undefined behaviour. \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming. \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: \remark * N is @c last - @c first, \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). */ template <class Range, class Right_shift> inline void integer_sort(Range& range, Right_shift shift) { integer_sort(boost::begin(range), boost::end(range), shift); } } } } #endif