Function template pdqsort_branchless

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

Synopsis

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


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

Description

pdqsort_branchless is a fast generic sorting algorithm that is similar in concept to introsort but runs faster on certain patterns. pdqsort_branchless 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 with block based partitioning, and pdqsort_branchless runs 80-90% faster than GCC 6.2's std::sort when sorting small data such as integers. However, this speedup is gained by totally bypassing the branch predictor, if your comparison operator or iterator contains branches you will most likely see little gain or a small loss in performance.

	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