A lightweight, zero-dependency crate that provides an efficient nth_element implementation in Rust based on Andrei Alexandrescu’s Adaptive Quickselect algorithm.
Available on crates.io.

Add the crate to your Cargo.toml:

[dependencies]
adqselect = "0.1.5"

use adqselect::nth_element;

fn main() {
    let mut v = vec![10, 7, 9, 7, 2, 8, 8, 1, 9, 4];
    nth_element(&mut v, 3, &mut Ord::cmp);

    assert_eq!(v[3], 7);
}

nth_element rearranges the vector so that the element at position n is the same as if the vector were fully sorted but runs in O(n) time on average.

The elements before index n are less than or equal to v[n], and those after are greater than or equal.

Based on the paper

Fast Deterministic Selection (Andrei Alexandrescu, 2016)

This algorithm refines the classic Median of Medians approach to achieve strong performance guarantees while remaining practical.

adqselect guarantees linear deterministic time complexity and is competitive with popular selection crates such as:

• floydrivest
• order-stat
• kth
• pdqselect

Detailed benchmarks are available in the repository, comparing throughput and allocation efficiency across datasets of varying size and distribution.

Licensed under the MIT License.

Results

Violin Plot

This chart shows the relationship between function/parameter and iteration time. The thickness of the shaded region indicates the probability that a measurement of the given function/parameter would take a particular length of time.

Line Chart

This chart shows the mean measured time for each function as the input (or the size of the input) increases.

adqselect on 1.000 random unsigned integers

adqselect on 10.000 random unsigned integers

adqselect on 100.000 random unsigned integers

adqselect on 1.000.000 random unsigned integers

floydrivest on 1.000 random unsigned integers

floydrivest on 10.000 random unsigned integers

floydrivest on 100.000 random unsigned integers

floydrivest on 1.000.000 random unsigned integers

kth on 1.000 random unsigned integers

kth on 10.000 random unsigned integers

kth on 100.000 random unsigned integers

kth on 1.000.000 random unsigned integers

order_stat on 1.000 random unsigned integers

order_stat on 10.000 random unsigned integers

order_stat on 100.000 random unsigned integers

order_stat on 1.000.000 random unsigned integers

pdqselect on 1.000 random unsigned integers

pdqselect on 10.000 random unsigned integers

pdqselect on 100.000 random unsigned integers

pdqselect on 1.000.000 random unsigned integers

This report was generated by Criterion.rs, a statistics-driven benchmarking library in Rust.