[−][src]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
In the current implementation maximum supported array length is
9223372036854775808
. Next power of two which is usize::MAX
is actually
264-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"]);