#075 Apr 11, 2026

75. select_nth_unstable — Find the Kth Element Without Sorting

You’re sorting an entire Vec just to grab the median or the top 3 elements. select_nth_unstable does it in O(n) — no full sort required.

The classic approach: sort everything, then index:

1
2
3
4
let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
scores.sort();
let median = scores[scores.len() / 2];
assert_eq!(median, 73);

That’s O(n log n) to answer an O(n) question. select_nth_unstable uses a partial-sort algorithm (quickselect) to put the element at a given index into its final sorted position — everything before it is smaller or equal, everything after is greater or equal:

1
2
3
4
let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
let mid = scores.len() / 2;
scores.select_nth_unstable(mid);
assert_eq!(scores[mid], 73);

The method returns three mutable slices — elements below, the pivot element, and elements above — so you can work with each partition directly:

1
2
3
4
5
6
7
let mut data = vec![10, 80, 30, 90, 50, 70, 20];
let (lower, median, upper) = data.select_nth_unstable(3);
// lower contains 3 elements all <= *median
// upper contains 3 elements all >= *median
assert_eq!(*median, 50);
assert!(lower.iter().all(|&x| x <= 50));
assert!(upper.iter().all(|&x| x >= 50));

Need the top 3 scores without sorting the full list? Select the boundary, then sort only the small tail:

1
2
3
4
5
6
let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
let k = scores.len() - 3;
scores.select_nth_unstable(k);
let top_3 = &mut scores[k..];
top_3.sort_unstable(); // sort only 3 elements, not all 7
assert_eq!(top_3, &[82, 91, 99]);

Custom ordering works too. Find the median by absolute value:

1
2
3
4
let mut vals = vec![-20, 5, -10, 15, -3, 8, 1];
let mid = vals.len() / 2;
vals.select_nth_unstable_by_key(mid, |v| v.abs());
assert_eq!(vals[mid].abs(), 8);

The “unstable” in the name means equal elements might be reordered (like sort_unstable) — it doesn’t mean the API is experimental. This is stable since Rust 1.49, available on any [T] where T: Ord.

This post is licensed under CC BY 4.0 by the author.