# 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’ 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.
- The RAJA CUDA back-end implementation only supports sorting arithmetic types using RAJA operators less and greater.

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 equivalent elements a_{i}
and a_{j} for any i != j where a_{i} appears before a_{j} if i < j

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

and calculates the stably sorted output sequence `y`

which preserves the order of
equivalent elements, in other words 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)`

`RAJA::sort< exec_policy >(iter, iter + N)`

`RAJA::sort< exec_policy >(iter, iter + N, comparator)`

For example sorting the `in`

array filled 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
```

by performing a sequential unstable sort operation using the following code:

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

fills 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 range of elements and `iter`

is a random access
iterator to a range of elements. `container`

and `iter`

provide access to the
input sequence and contain the output sequence at the end of sort. The first
and third sort operations above will be *non-decreasing* sorts since there is
no comparator argument given; i.e., the sequences will be reordered *in-place*
using operator::less. The second and fourth sorts will apply the comparator
that is passed into the function.

RAJA also provides sort pairs 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< exec_policy >(keys_iter, keys_iter + N, vals_iter)`

`RAJA::sort_pairs< exec_policy >(keys_iter, keys_iter + N, vals_iter, comparator)`

Sort pairs generates the same output sequence of keys in `keys_container`

or
`keys_iter`

as sort does in `container`

or `iter`

and also reorders the sequence
of values in `vals_container`

or `vals_iter`

by permuting the sequence of values
in the same manner as the sequence of keys; i.e. sorting the sequence of pairs
based on their keys. Note that the `comparator`

used in sort_pairs only compares
keys.

## RAJA Stable Sorts¶

Using RAJA stable sorts is essentially the same as unstable sorts:

`RAJA::stable_sort< exec_policy >(container)`

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

`RAJA::stable_sort< exec_policy >(iter, iter + N)`

`RAJA::stable_sort< exec_policy >(iter, iter + N, 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::stable_sort_pairs< exec_policy >(keys_iter, keys_iter + N, vals_iter)`

`RAJA::stable_sort_pairs< exec_policy >(keys_iter, keys_iter + N, vals_iter, 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`

.