Crate tinysort

This is the documentation for tinysort - a truly minimal memory use sort implementation

This crate exposes a single API, the struct TinySort. You can create an instance with the TinySort::new method, which requires 3 parameters: allowed overhead, amount of values and the maximum value to sort.

• Allowed overhead: The allowed overhead, in units of four bytes, that the algorithm is allowed to use on top of the theoretically required amount of memory. Smaller values means the algorithm becomes slower.
• Amount of values: The amount of values you want this sorter to sort maximally. Going over this limit will cause the sorter to run out of memory and panic.
• The maximum value to be sorted. This is required for the sorter's memory calculation to function properly. Trying to sort values above this value can cause the sorter to run out of memory and panic

Example

use tinysort::TinySort;
 
let mut sort = TinySort::new(8000, 1_000_000, 100_000_000).unwrap();
 
// create some values to sort between the indicated borders
let mut values: Vec<u32> = (0 .. 1_000_000).map(|i| (100_000_000.0 * (i as f64 * 0.4567895678).fract()) as u32).collect();
for value in values.iter().cloned() {
     sort.insert(value);
}
 
println!("TinySort using {} bytes of memory, normal sort using {} bytes of memory.", sort.used_space(), values.len() * std::mem::size_of::<u32>());

let sorted: Vec<u32> = sort.into_iter().collect();
values.sort_unstable();
assert!(sorted == values);

This example will print TinySort using 1043916 bytes of memory, normal sort using 4000000 bytes of memory., showing the almost 4x memory usage drop thanks to TinySort.

Structs

TinySort	A truly memory-efficient sort implementation.
TinySortIterator	An iterator over the contents of a tinysort. It yields the sorted values from small to large. Created via the TinySort::into_iter method.