cub::UnstablePairwiseSort#

template<typename KeyT, typename ValueT, typename CompareOp, int ItemsPerThread>
inline void cub::UnstablePairwiseSort(
KeyT (&keys)[ItemsPerThread],
ValueT (&items)[ItemsPerThread],
CompareOp compare_op
)#

Sorts data using Ian Parberry’s unstable pairwise sorting network.

The algorithm has \(O(N \log^2 N)\) complexity and supports any positive number of items, including non-powers of two.

See also

Ian Parberry, “The Pairwise Sorting Network”, Parallel Processing Letters, Vol. 2, No. 2-3, pp. 205-211, 1992. https://ianparberry.com/pubs/pairwise.pdf

Note

The algorithm is particularly useful for order-statistic selection, such as median and top-k. The compiler can eliminate unnecessary operations when only a subset of the output is consumed.

Template Parameters:

  • KeyT – Key type.

  • ValueT – Value type. If cub::NullType is used, only keys are sorted.

  • CompareOp – Comparison function object that provides a strict weak ordering.

  • ItemsPerThread – Number of items per thread.

Parameters:

  • keys – [inout] Keys to sort.

  • items – [inout] Values to reorder with their corresponding keys.

  • compare_op – [in] Comparison function object.

On this page