slice::select_nth_unstable has O(n^2) complexity, docs claim O(n) worst case

[orlp]

To reproduce, run the following program:

use std::cmp::Ordering;

fn prepare_worst_case(n: usize) -> Vec<u64> {
    let mut values = vec![None; n];
    let mut indices: Vec<usize> = (0..n).collect();
    let mut ctr = 0;

    indices.select_nth_unstable_by(n-2, |lhs, rhs| {
        match (values[*lhs], values[*rhs])  {
            (None, None) => {
                values[*lhs] = Some(ctr);
                ctr += 1;
                Ordering::Less
            },
            (None, Some(_)) => Ordering::Greater,
            (Some(_), None) => Ordering::Less,
            (Some(a), Some(b)) => a.cmp(&b),
        }
    });

    values.into_iter().map(|v| v.unwrap_or(ctr)).collect()
}

fn main() {
    for n in [1000, 10000, 100000] {
        let mut worst_case = prepare_worst_case(n);

        // Note: quadratic behavior triggered strictly by previously crafted malicious input,
        // no special comparison function used here.
        let mut calls = 0;
        worst_case.select_nth_unstable_by_key(n - 2, |x| { calls += 1; *x });
        println!("{}: {}", n, calls);
    }
}

Running this program on the latest stable or nightly Rust we get output:

1000: 195172
10000: 18821756
100000: 1875713006

Multiplying the input size by 10 increases the number of comparisons by a factor of 100 - clearly quadratic.

Looking into the code, currently the implementation of select_nth_unstable uses pure quickselect, explaining the quadratic behavior. To get guaranteed linear time behavior there needs to be a median-of-medians fallback in case the number of iterations of quickselect becomes too large.

[SamB]

Isn't this a dupe of:

• select_nth_unstable has quadratic worst-case time complexity; docs claim it should be linear #102451

[orlp]

@SamB No, that is a dupe of this issue, this one predates it. Nevertheless, this can be closed.