Sorting and Searching

Rust slices ([T]) provide built-in, production-grade sorting and selection algorithms in the standard library—supporting stable and unstable sorting, custom key projections, descending order via Reverse, and linear-time $O(n)$ order statistics (select_nth_unstable).

Standard Library Slice Sorting & Selection Methods:

  ├── `slice.sort()`                 Stable O(n log n) Driftsort / Merge-sort (allocates scratch buffer)
  ├── `slice.sort_unstable()`        Unstable O(n log n) ipnsort (Zero heap allocation! Faster!)
  ├── `slice.sort_by_key(|x| ...)`   Sorts by extracted key `K: Ord`
  ├── `slice.sort_by(|a, b| ...)`    Sorts by custom `Ordering` comparator
  └── `slice.select_nth_unstable(k)` O(n) Quickselect: places k-th smallest at `slice[k]`!

Comparing sort() (Stable) and sort_unstable() (Unstable)

Multi-Criteria Tuple Sorting, Descending Sort, and Floating-Point Sort

1. Lexicographical Tuple Sorting: Tuples (A, B, C) implement Ord lexicographically (comparing A first, then B on ties, then C).
2. Descending Sort (std::cmp::Reverse): Wrapping a key in Reverse(key) sorts that field in descending order (b.cmp(a)), making mixed ascending/descending sorts trivial (sort_unstable_by_key(|x| (Reverse(x.score), x.name))).
3. Sorting Floating-Point Numbers (f64::total_cmp): Because f32 and f64 only implement PartialOrd (not Ord, due to NaN), use a.total_cmp(b) inside sort_unstable_by:

use std::cmp::Reverse;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Candidate {
    pub name: &'static str,
    pub score: u32,
    pub penalty_time: u32,
}

pub fn rank_candidates(candidates: &mut [Candidate]) {
    // Sort by:
    //   1. `score` DESCENDING (`Reverse(c.score)`)
    //   2. `penalty_time` ASCENDING (`c.penalty_time`)
    //   3. `name` ASCENDING (`c.name`)
    candidates.sort_unstable_by_key(|c| (Reverse(c.score), c.penalty_time, c.name));
}

fn main() {
    let mut board = vec![
        Candidate { name: "bob", score: 300, penalty_time: 45 },
        Candidate { name: "alice", score: 400, penalty_time: 60 },
        Candidate { name: "carol", score: 300, penalty_time: 30 },
    ];

    rank_candidates(&mut board);
    let names: Vec<&str> = board.iter().map(|c| c.name).collect();
    assert_eq!(names, vec!["alice", "carol", "bob"]);
    println!("Ranked leaderboard: {names:?}");

    // Sorting `f64` slices safely using `f64::total_cmp`:
    let mut floats = [3.14f64, -1.0, 2.71, 0.0];
    floats.sort_unstable_by(f64::total_cmp);
    assert_eq!(floats, [-1.0, 0.0, 2.71, 3.14]);

    // Finding the median (index 2 of 5 elements) in O(n) time without full sorting:
    let mut nums = [90, 10, 50, 30, 70];
    let (_lesser, median, _greater) = nums.select_nth_unstable(2);
    assert_eq!(*median, 50);
    println!("Sorted floats: {floats:?}, O(n) median: {median}");
}

Ranked leaderboard: ["alice", "carol", "bob"]
Sorted floats: [-1.0, 0.0, 2.71, 3.14], O(n) median: 50

Coordinate Compression in $O(n \log n)$ Time

When an algorithm receives $N \le 10^5$ large values in the range $0..=10^{18}$ (for example, to insert into a Fenwick Tree or Segment Tree), coordinate compression maps each value to its dense rank in 0..unique_count using sort_unstable(), dedup(), and binary_search():

pub fn compress_coordinates(values: &[i64]) -> Vec<usize> {
    let mut sorted = values.to_vec();
    sorted.sort_unstable();
    sorted.dedup();
    values
        .iter()
        .map(|x| sorted.binary_search(x).unwrap())
        .collect()
}