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.

See Also