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.

Installation

Add the crate to your Cargo.toml:

[dependencies]
adqselect = "0.1.5"

Usage

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.

Implementation

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.

Performance

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

• floydrivest
• order-stat
• kth
• pdqselect

Benchmarks

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

License

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.