Function sort_by_cached_key

pub fn sort_by_cached_key<T, F, K>(slice: &mut [T], key_fn: F)
where
    F: FnMut(&T) -> K,
    K: Key,

Sorts the slice indirectly, using a key extraction function and caching the keys.

Key can be any scalar type. See Key for a full list.

This sort is stable (i.e., does not reorder equal elements) and O(m n + w n), where the key function is O(m).

This function can be significantly faster for sorting by an expensive key function or for sorting large elements. The keys are extracted, sorted, and then the elements of the slice are reordered in-place. This saves CPU cycles in case of an expensive key function and saves memory bandwidth in case of large elements.

For sorting small elements by simple key functions (e.g., functions that are property accesses or basic operations), sort_by_key is likely to be faster.

In the worst case, allocates temporary storage in a Vec<(K, usize)> twice the length of the slice.

Examples

let mut data = ["-6", "2", "15", "-1", "0"];

radsort::sort_by_cached_key(&mut data, |s| s.parse::<i32>().unwrap());

assert_eq!(data, ["-6", "-1", "0", "2", "15"]);