# Sorts¶

RAJA provides portable parallel sort operations, which are basic parallel algorithm building blocks. They are described in this section.

A few important notes:

Note

• All RAJA sort operations are in the namespace RAJA.
• Each RAJA sort operation is a template on an execution policy parameter. The same policy types used for RAJA::forall methods may be used for RAJA sorts.
• RAJA sort operations accept an optional comparator argument so users can perform different types of sort operations. If no operator is given, the default is a less than operation and the result is non-decreasing.

Also:

Note

• For sorts using the CUDA back-end, RAJA uses the implementations provided by the NVIDIA CUB library. For information please see build-external-tpl.
• For sorts using the HIP back-end, RAJA uses the implementations provided by the AMD rocPRIM library. For information please see build-external-tpl.
• The RAJA CUDA and HIP back-ends only support sorting arithmetic types using RAJA operators ‘less than’ and ‘greater than’.

Please see the Parallel Sort Operations tutorial section for usage examples of RAJA sort operations.

## Sort Operations¶

In general, a sort operation takes a sequence of numbers x and a binary comparison operator op that forms a strict weak ordering of elements in input sequence x and produces a sequence of numbers y as output. The output sequence is a permutation of the input sequence where each pair of elements a and b, where a is before b in the output sequence, satisfies !(b op a). Sorts are stable if they always preserve the order of equivalent elements, where equivalent elements satisfy !(a op b) && !(b op a).

A stable sort takes an input sequence x where ai appears before aj if i < j when ai and aj are equivalent for any i != j.

x = { a0, b0, a1, … }

and calculates the stably sorted output sequence y that preserves the order of equivalent elements. That is, the sorted sequence where element ai appears before the equivalent element aj if i < j:

y = { a0, a1, b0, … }

An unstable sort may not preserve the order of equivalent elements and may produce either of the following output sequences:

y = { a0, a1, b0, … }

or

y = { a1, a0, b0, … }

## RAJA Unstable Sorts¶

RAJA unstable sort operations look like the following:

• RAJA::sort< exec_policy >(container)
• RAJA::sort< exec_policy >(container, comparator)

For example, sorting an array with this sequence of values:

6 7 2 1 0 9 4 8 5 3 4 9 6 3 7 0 1 8 2 5


with a sequential unstable sort operation:

  RAJA::sort<RAJA::seq_exec>(RAJA::make_span(out, N));


produces the out array with this sequence of values:

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9


Note that the syntax is essentially the same as Parallel Scan Operations. Here, container is a random access range of elements. container provides access to the input sequence and contains the output sequence at the end of sort. The first sort operation listed above will be a non-decreasing sort since there is no comparator argument given; i.e., the sequences will be reordered in-place using operator::less. The second sort will apply the comparator that is passed into the function. Note that the container argument can be generated from iterators using RAJA::make_span(begin, len).

RAJA also provides sort operations that operate on key-value pairs stored separately:

• RAJA::sort_pairs< exec_policy >(keys_container, vals_container)
• RAJA::sort_pairs< exec_policy >(keys_container, vals_container, comparator)

RAJA::sort_pairs methods generate the same output sequence of keys in keys_container as RAJA::sort does in container and reorders the sequence of values in vals_container by permuting the sequence of values in the same manner as the sequence of keys; i.e. the sequence of pairs is sorted based on comparing their keys.

Note

The comparator used in RAJA::sort_pairs only compares keys.

## RAJA Stable Sorts¶

RAJA stable sorts are essentially the same as unstable sorts:

• RAJA::stable_sort< exec_policy >(container)
• RAJA::stable_sort< exec_policy >(container, comparator)

RAJA also provides stable sort pairs that operate on key-value pairs stored separately:

• RAJA::stable_sort_pairs< exec_policy >(keys_container, vals_container)
• RAJA::stable_sort_pairs< exec_policy >(keys_container, vals_container, comparator)

## RAJA Comparison Operators¶

RAJA provides two operators that can be used to produce different ordered sorts:

• RAJA::operators::less<T>
• RAJA::operators::greater<T>

Note

All RAJA comparison operators are in the namespace RAJA::operators.

## Sort Policies¶

For information about RAJA execution policies to use with sort operations, please see Policies.