## Abstract

A non-comparison-based sort that sorts an array in O(k n) work and O(k log(n)) span, where k is the number of bits in each element.

Generally, this is the sorting function we recommend for Futhark programs, but be careful about negative integers (use `radix_sort_int`) and floating-point numbers (use `radix_sort_float`). If you need a comparison-based sort, consider `merge_sort`.

## Synopsis

 val radix_sort [n] 't : (num_bits: i32) -> (get_bit: i32 -> t -> i32) -> (xs: [n]t) -> [n]t val with_indices [n] 'a : (xs: [n]a) -> [n](a, i64) val radix_sort_by_key [n] 't 'k : (key: t -> k) -> (num_bits: i32) -> (get_bit: i32 -> k -> i32) -> (xs: [n]t) -> [n]t val radix_sort_int [n] 't : (num_bits: i32) -> (get_bit: i32 -> t -> i32) -> (xs: [n]t) -> [n]t val radix_sort_int_by_key [n] 't 'k : (key: t -> k) -> (num_bits: i32) -> (get_bit: i32 -> k -> i32) -> (xs: [n]t) -> [n]t val radix_sort_float [n] 't : (num_bits: i32) -> (get_bit: i32 -> t -> i32) -> (xs: [n]t) -> [n]t val radix_sort_float_by_key [n] 't 'k : (key: t -> k) -> (num_bits: i32) -> (get_bit: i32 -> k -> i32) -> (xs: [n]t) -> [n]t

## Description

val radix_sort [n] 't: (num_bits: i32) -> (get_bit: i32 -> t -> i32) -> (xs: [n]t) -> [n]t

The `num_bits` and `get_bit` arguments can be taken from one of the numeric modules of module type `integral` or `float`, such as `i32` or `f64`. However, if you know that the input array only uses lower-order bits (say, if all integers are less than 100), then you can profitably pass a smaller `num_bits` value to reduce the number of sequential iterations.

Warning: while radix sort can be used with numbers, the bitwise representation of of both integers and floats means that negative numbers are sorted as greater than non-negative. Negative floats are further sorted according to their absolute value. For example, radix-sorting `[-2.0, -1.0, 0.0, 1.0, 2.0]` will produce `[0.0, 1.0, 2.0, -1.0, -2.0]`. Use `radix_sort_int` and `radix_sort_float` in the (likely) cases that this is not what you want.

val with_indices [n] 'a: (xs: [n]a) -> [n](a, i64)
val radix_sort_by_key [n] 't 'k: (key: t -> k) -> (num_bits: i32) -> (get_bit: i32 -> k -> i32) -> (xs: [n]t) -> [n]t

Like `radix_sort`, but sort based on key function.

val radix_sort_int [n] 't: (num_bits: i32) -> (get_bit: i32 -> t -> i32) -> (xs: [n]t) -> [n]t

A thin wrapper around `radix_sort` that ensures negative integers are sorted as expected. Simply pass the usual `num_bits` and `get_bit` definitions from e.g. `i32`.

val radix_sort_int_by_key [n] 't 'k: (key: t -> k) -> (num_bits: i32) -> (get_bit: i32 -> k -> i32) -> (xs: [n]t) -> [n]t

Like `radix_sort_int`, but sort based on key function.

val radix_sort_float [n] 't: (num_bits: i32) -> (get_bit: i32 -> t -> i32) -> (xs: [n]t) -> [n]t

A thin wrapper around `radix_sort` that ensures floats are sorted as expected. Simply pass the usual `num_bits` and `get_bit` definitions from `f32` and `f64`.

val radix_sort_float_by_key [n] 't 'k: (key: t -> k) -> (num_bits: i32) -> (get_bit: i32 -> k -> i32) -> (xs: [n]t) -> [n]t

Like `radix_sort_float`, but sort based on key function.

• `merge_sort`