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
andget_bit
arguments can be taken from one of the numeric modules of module typeintegral
orfloat
, such asi32
orf64
. 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 smallernum_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]
. Useradix_sort_int
andradix_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 usualnum_bits
andget_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 usualnum_bits
andget_bit
definitions fromf32
andf64
.- ↑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.
See Also
merge_sort