Function sorting_rs::bitonic_sort::bitonic_sort

pub fn bitonic_sort<T: PartialOrd + Default + Clone>(input: &mut Vec<T>)

Sorts a slice in-place using Bitonic sort. All kinds of slices can be sorted as long as they implement PartialOrd.

Bitonic sort is one of the fastest sorting networks. Sorting network has the sequence of comparisons that are not data-dependent.

Default implementations of this algorithm demand power of two elements in array, but for API consistency any length is supported in case of this implementation. This flexibility comes at cost though: the least effective operation is Vec::drain(..index), which removes additional values from the beginning of Vec. Also algotithm has to place new instances to make array compatible with logic.

In the current implementation maximum supported array length is 9223372036854775808. Next power of two which is usize::MAX is actually 2⁶⁴-1, but isn't supported in most of known cases anyway, as it occupies 147.6 exabytes of memory.

Performance-wise all the available 64 bit powers of two are calculated and placed into const.

Examples

let mut vec = vec![5,3,2,4];
sorting_rs::bitonic_sort(&mut vec);
assert_eq!(vec, &[2,3,4,5]);

let mut strings = vec!["rustc", "cargo", "rustup"];
sorting_rs::bitonic_sort(&mut strings);
assert_eq!(strings, &["cargo", "rustc", "rustup"]);