Function pdqselect::select_by_key

pub fn select_by_key<T, B, F>(v: &mut [T], k: usize, f: F) where
    F: FnMut(&T) -> B,
    B: Ord, 

Partially sorts a slice using f to extract a key to compare elements by and puts the kth smallest item in place.

This sort is in-place, unstable, and O(n log n) worst-case.

The implementation is based on Orson Peters’ pattern-defeating quicksort.

Examples

let mut v = [-5i32, 4, 1, -3, 2];
let k = 3;
pdqselect::select_by_key(&mut v, k, |x| x.abs());
assert!(v[..k].iter().all(|&x| x.abs() <= v[k].abs()));
assert!(v[k+1..].iter().all(|&x| x.abs() >= v[k].abs()));