Function template pdqsort

boost::sort::pdqsort — Generic sort algorithm using random access iterators.

Synopsis

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


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

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 partitioning has been very efficiently implemented, and pdqsort runs 80-90% faster than GCC 6.2's std::sort. If the type being sorted is std::is_arithmetic this function will automatically use pdqsort_branchless.

	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.

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