// 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, typename iterator_traits< RandIt >::size_type 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.
RandIt must meet the requirements of ValueSwappable and RandomAccessIterator.
The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible.
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.