Vec<T> in Depth

Sorting Vectors

Through deref coercion to [T], Vec<T> provides two complete families of $O(n \log n)$ sorting methods: stable sorts (.sort(), .sort_by(), .sort_by_key(), .sort_by_cached_key()) and unstable sorts (.sort_unstable(), .sort_unstable_by(), .sort_unstable_by_key()).

Stable vs. Unstable Sorting Methods

Method Stable? (Preserves Order of Equal Elements) Auxiliary Heap Allocation Required Bounds
v.sort() Yes (driftsort) Up to $O(n)$ scratch space T: Ord
v.sort_by(cmp) Yes Up to $O(n)$ scratch space cmp: FnMut(&T, &T) -> Ordering
v.sort_by_key(k) Yes Up to $O(n)$ scratch space k: FnMut(&T) -> K, K: Ord
v.sort_by_cached_key(k) Yes $O(n)$ key cache + scratch space Computes k(&elem) once per element
v.sort_unstable() No (ipnsort) Zero (0 bytes, in-place) T: Ord
v.sort_unstable_by(cmp) No Zero (0 bytes, in-place) cmp: FnMut(&T, &T) -> Ordering
v.sort_unstable_by_key(k) No Zero (0 bytes, in-place) k: FnMut(&T) -> K, K: Ord

For primitive types (i32, u64, char) where equal values are indistinguishable, v.sort_unstable() is strictly faster and uses zero extra heap memory.

Sorting Ascending, Descending, by Key, and Multi-Field

use std::cmp::Reverse;

#[derive(Debug)]
struct Task {
    priority: u8,
    name: &'static str,
}

fn main() {
    // 1. Fast in-place unstable sort on primitives:
    let mut nums = vec![42, 7, 19, 7, 3];
    nums.sort_unstable();
    println!("Ascending:  {nums:?}");

    // 2. Descending sort using `std::cmp::Reverse`:
    nums.sort_unstable_by_key(|&n| Reverse(n));
    println!("Descending: {nums:?}");

    // 3. Stable sort by key (preserves original relative order of ties):
    let mut tasks = vec![
        Task { priority: 2, name: "backup" },
        Task { priority: 1, name: "auth" },
        Task { priority: 2, name: "cleanup" },
    ];
    tasks.sort_by_key(|t| t.priority);
    println!("Tasks by priority: {tasks:?}");
}

Ascending:  [3, 7, 7, 19, 42]
Descending: [42, 19, 7, 7, 3]
Tasks by priority: [Task { priority: 1, name: "auth" }, Task { priority: 2, name: "backup" }, Task { priority: 2, name: "cleanup" }]

Sorting Floating-Point Vectors (f64::total_cmp)

Because f32 and f64 implement PartialOrd rather than Ord (due to NaN), calling .sort() directly on a Vec<f64> does not compile. Pass f64::total_cmp (or f32::total_cmp) to .sort_by() or .sort_unstable_by():

fn main() {
    let mut measurements = vec![3.5_f64, -1.2, 0.0, 9.8, 2.1];
    measurements.sort_unstable_by(f64::total_cmp);

    println!("Sorted floats: {measurements:?}");
}

Sorted floats: [-1.2, 0.0, 2.1, 3.5, 9.8]

Partial Sorting in $O(n)$ Time (select_nth_unstable)

If you only need the $k$-th smallest element or the top $k$ smallest elements without sorting the entire vector, v.select_nth_unstable(k) (Quickselect / Introselect) partitions the slice in $O(n)$ average time so that v[k] is in its final sorted position, all elements in v[..k] are $\le v[k]$, and all elements in v[k + 1..] are $\ge v[k]$.