# 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 a_{i} appears
before a_{j} if i < j when a_{i} and a_{j} are equivalent for
any i != j.

x = { a_{0}, b_{0}, a_{1}, … }

and calculates the stably sorted output sequence `y`

that preserves the
order of equivalent elements. That is, the sorted sequence where element
a_{i} appears before the equivalent element a_{j} if i < j:

y = { a_{0}, a_{1}, b_{0}, … }

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

y = { a

_{0}, a_{1}, b_{0}, … }or

y = { a

_{1}, a_{0}, b_{0}, … }

## 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`

.