Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards


Function template 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, 
                     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.