Function sorting_rs::smooth_sort::smooth_sort

pub fn smooth_sort<T: PartialOrd>(input: &mut [T])

Sorts a slice in-place using Smooth sort

All kinds of slices can be sorted as long as they implement PartialOrd.

This sorting algorithm transforms the input array into implicit heap data structure and then produces the sorted array by repeatedly extracting the largest remaining element This algorithm makes use of Leonardo numbers. It's a sequence of numbers defined by:

L(0) = 1
L(1) = 1
L(n) = L(n - 1) + L(n - 2) + 1
*OR*
L(n) = 2 * Fib(n + 1) - 1

Where + 1 is "add" number and "Fib" are Fibonacci numbers

For 64-bit systems it's possible to use 90 Leonardo numbers placed as a constant array [usize; 90]

Examples

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

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