Function template pdqsort

boost::sort::pdqsort — Generic sort algorithm using random access iterators and a user-defined comparison operator.

Synopsis

// In header: <boost/sort/pdqsort/pdqsort.hpp>


template<typename Iter, typename Compare> 
  void pdqsort(Iter first, Iter last, Compare comp);

Description

pdqsort is a fast generic sorting algorithm that is similar in concept to introsort but runs faster on certain patterns. pdqsort is in-place, unstable, deterministic, has a worst case runtime of O(N * lg(N)) and a best case of O(N). Even without patterns, the quicksort has been very efficiently implemented, and pdqsort runs 1-5% faster than GCC 6.2's std::sort. If the type being sorted is std::is_arithmetic and Compare is std::less or std::greater this function will automatically use pdqsort_branchless for far greater speedups.

	Warning
	Invalid arguments cause undefined behaviour.

	Warning
	Throwing an exception may cause data loss.

Parameters:

`first`	Iterator pointer to first element.
`last`	Iterator pointing to one beyond the end of data.
`comp`	A binary functor that returns whether the first element passed to it should go before the second in order.

Requires:

[first, last) is a valid range.

Requires:

RandomAccessIter value_type is MoveAssignable

Requires:

RandomAccessIter value_type is MoveConstructible

Requires:

RandomAccessIter value_type is LessThanComparable

Postconditions:

The elements in the range [first, last) are sorted in ascending order.

Returns:

void.

Throws:

std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), functors, or any operations on iterators throw.

Boost C++ Libraries