...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::movelib::adaptive_sort
// In header: <boost/move/algo/adaptive_sort.hpp> template<typename RandIt, typename RandRawIt, typename Compare> void adaptive_sort(RandIt first, RandIt last, Compare comp, RandRawIt uninitialized, std::size_t uninitialized_len);
Effects: Sorts the elements in the range [first, last) in ascending order according to comparison functor "comp". The sort is stable (order of equal elements is guaranteed to be preserved). Performance is improved if additional raw storage is provided.
Requires:
RandIt must meet the requirements of ValueSwappable and RandomAccessIterator.
The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible.
Parameters:
first, last: the range of elements to sort
comp: comparison function object which returns true if the first argument is is ordered before the second.
uninitialized, uninitialized_len: raw storage starting on "uninitialized", able to hold "uninitialized_len" elements of type iterator_traits<RandIt>::value_type. Maximum performance is achieved when uninitialized_len is ceil(std::distance(first, last)/2).
Throws: If comp throws or the move constructor, move assignment or swap of the type of dereferenced RandIt throws.
Complexity: Always K x O(Nxlog(N)) comparisons and move assignments/constructors/swaps. Comparisons are close to minimum even with no additional memory. Constant factor for data movement is minimized when uninitialized_len is ceil(std::distance(first, last)/2). Pretty good enough performance is achieved when ceil(sqrt(std::distance(first, last)))*2.
Caution: Experimental implementation, not production-ready.