Sorting in Rust Stable Versus Unstable and Their Costs

Rust's slices have six sort methods, and choosing among them is two questions: do equal elements need to keep their order, and is the key cheap. Answering them correctly avoids both a behavior bug and a hidden quadratic cost. This post lays out the methods with code and a table, and keeps from quoting speed ratios you cannot verify without your data. It is a decision piece in the performance cluster; the profiler workflow is in profiling Rust programs.

Rust 1.90, edition 2024.

The methods

fn main() {
    let mut v = vec![("b", 2), ("a", 2), ("c", 1)];

    v.sort_by_key(|&(_, n)| n);          // stable
    println!("{v:?}");

    let mut w = vec![("b", 2), ("a", 2), ("c", 1)];
    w.sort_unstable_by_key(|&(_, n)| n); // may reorder equal keys
    println!("{w:?}");
}

The first prints [("c", 1), ("b", 2), ("a", 2)]: the two entries with key 2 keep their input order, b before a. The second may print the same, or [("c", 1), ("a", 2), ("b", 2)]; the unstable sort makes no promise.

Recent standard libraries use new sort implementations (driftsort for the stable sort and ipnsort for the unstable sort since Rust 1.81), which made both faster on many inputs. Treat older benchmarks with suspicion.

The expensive key trap

let mut names = vec!["Zed", "amy", "Bob"];
names.sort_by_key(|s| s.to_lowercase());   // allocates in every comparison
names.sort_by_cached_key(|s| s.to_lowercase()); // once per element

With n names, the first allocates about 2 n log n strings, the second n. When the key function allocates or does real work, use the cached variant. When the key is a field, the plain version is fine. A related restriction: sort_by_key cannot return a reference to the element, since the key's lifetime does not fit; use sort_by(|a, b| a.name.cmp(&b.name)) for borrowed keys.

Floats

f64 is only PartialOrd, because of NaN. This does not compile:

error[E0277]: the trait bound `f64: Ord` is not satisfied

Use the total order: v.sort_by(|a, b| a.total_cmp(b));. NaNs sort to the ends, depending on sign. partial_cmp(...).unwrap() panics when a NaN is present.

Choosing

1. Equal elements indistinguishable (integers, strings compared whole)? sort_unstable.
2. Sorting records by one field, with an earlier order to keep? sort_by_key.
3. Key expensive? sort_by_cached_key.
4. Memory tight and stability needed? Think about sorting indices, or sort by a composite key (field, original_index) with the unstable sort.

Beyond sorting

If you only need the top k, select_nth_unstable partitions in linear time, and a BinaryHeap handles streaming top k. For sorted lookups on a static set, keep the Vec sorted and use binary_search. Benchmark both forms on your data shape, and see benchmarking pitfalls for how to avoid being fooled. The standard library documents the guarantees on the slice sort method.