Algorithms to find the K-th order element

The k-th order element is the element which would be at the k-th index if the array was sorted.

Finding the median is a special case of finding the k-th order element, to find the median, select k to be half the array length.

Partitioning is commonly performed when searching for the K-th order element. An array is partitioned if all elements before a given element X are less than X, and all elements after a that same element X are greater than X.

Example

use kth::SliceExtKth;

let mut x = [6, 6, 8 ,1, 2];
// sorted =  1  2  6  6  8
let m = x.len()/2;
x.partition_by_kth(m);
println!("Median is {}", x[m]);
assert_eq!(x[x.len()/2], 6);

kth

Methods for partitioning arrays & finding the k-th order element.

The median is the element with order equal to half of the array length.

crates.io

travis-ci

docs (release)

docs (master)

Rust RFC issue #1470 talks about adding a similar interface.