Sorting and Ordering

Sorting looks trivial until the first .sort() on a Vec<f64> won't compile, or you need "by last name, then first name, descending by age." Rust's ordering story is built on two traits, Ord and PartialOrd, and a family of slice methods that let you sort by a key, a custom comparator, or the type's natural order. This tutorial covers picking the right sort_* method, why floats are special, and composing multi-field comparisons cleanly, the everyday operations that trip people up precisely because the naive approach almost works.

sort vs sort_by_key vs sort_by

Three methods cover almost every case, and reaching for the right one is mostly about how much you need to say:

let mut nums = vec![3, 1, 4, 1, 5];

// sort(): the type's natural Ord order — ascending
nums.sort();                          // [1, 1, 3, 4, 5]

// sort_by_key(): sort by a derived key, when elements aren't directly comparable how you want
let mut words = vec!["hello", "hi", "hey"];
words.sort_by_key(|s| s.len());       // by length: ["hi", "hey", "hello"]

// sort_by(): a full custom comparator returning Ordering
let mut people = vec![("Alice", 30), ("Bob", 25)];
people.sort_by(|a, b| a.1.cmp(&b.1)); // by age via explicit comparison

The rule: use sort() for the natural order, sort_by_key() when you can express the ordering as "compare by this extracted value", and sort_by() only when the comparison is too complex for a single key (reverse, multi-field, computed). Prefer sort_by_key over sort_by when both work, it's shorter and harder to get wrong (no chance of an inconsistent comparator).

Gotcha: sort_by_key calls the key function on every comparison, not once per element. If the key is expensive to compute (allocates, parses, hashes), that cost is paid O(n log n) times. When the key is costly, use sort_by_cached_key, which computes each key exactly once and caches it. For cheap keys (.len(), a field access) plain sort_by_key is fine; the cache only pays off when key extraction is the bottleneck.

Stable vs Unstable: sort vs sort_unstable

Every sort_* method has a sort_unstable* twin. The difference is whether equal elements keep their original relative order. sort is stable (equal elements stay in input order) but allocates temporary memory; sort_unstable is not stable but is faster and allocates nothing.

let mut v = vec![5, 3, 5, 1];
v.sort_unstable();        // faster; don't care about ties' relative order

Reach for sort_unstable by default when elements are simple values (integers, where two equal 5s are indistinguishable anyway, so stability is meaningless). Use stable sort when you're sorting records by one field and want ties to preserve a previous ordering, e.g. sort by department, having already sorted by name, and expect same-department entries to stay name-sorted. Stability only matters when "equal" elements are actually distinguishable in some other way.

Ord and PartialOrd: What #[derive] Gives You

For your own types, #[derive(PartialOrd, Ord)] makes them sortable. The derived order is lexicographic by field declaration order, it compares the first field, and only if those are equal moves to the second, and so on. This is often exactly what you want, and it means field order in the struct determines sort priority:

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Version {
    major: u32,   // compared first
    minor: u32,   // then this, on major tie
    patch: u32,   // then this
}
// Version { 1, 2, 0 } < Version { 1, 3, 0 } — derived, no hand-written cmp

Ord requires Eq (and PartialOrd requires PartialEq), so you derive all four together. The distinction between the two: Ord is a total order (every pair is comparable), while PartialOrd allows "these two aren't comparable" by returning None. Almost all types are totally ordered, the famous exception is floats.

The Float Problem

f64 and f32 implement PartialOrd but not Ord, which is why vec![1.0, 2.0].sort() fails to compile. The reason is NaN: it's not equal to anything, not even itself, and not greater or less than any number, so floats can't form the total order Ord demands.

let mut v = vec![3.0, 1.0, 2.0];

// v.sort();  // ERROR: the trait `Ord` is not implemented for `f64`

// use total_cmp: a total ordering over ALL f64 values, including NaN
v.sort_by(|a, b| a.total_cmp(b));   // [1.0, 2.0, 3.0]

Gotcha: don't reach for a.partial_cmp(b).unwrap() to sort floats, it panics the instant a NaN appears in the data, which is exactly the case that's hard to test for. Use f64::total_cmp (stable since Rust 1.62), which defines a total order over every float including NaN and infinities, so the sort can never panic. If NaN is genuinely invalid input, reject it at the boundary (TryFrom and Fallible Conversions) rather than letting partial_cmp().unwrap() blow up mid-sort.

Composing Comparisons: Reverse and Multi-Key

Real sorts are often "by X, then by Y, one of them descending." Two tools compose cleanly without a tangled custom comparator. std::cmp::Reverse flips one key's direction; Ordering::then_with chains a tiebreaker:

use std::cmp::Reverse;

let mut people = vec![
    ("Smith", "Alice", 30),
    ("Smith", "Bob", 25),
    ("Jones", "Carol", 40),
];

// by last name asc, then first name asc, then age DESC
people.sort_by(|a, b| {
    a.0.cmp(b.0)                              // last name
        .then_with(|| a.1.cmp(b.1))           // tie → first name
        .then_with(|| b.2.cmp(&a.2))          // tie → age descending (note b vs a)
});

// simpler when a single key with Reverse suffices:
people.sort_by_key(|p| (p.0, p.1, Reverse(p.2)));  // last, first, age-desc

then_with only evaluates the next comparison when the previous one was Equal, so it reads as a priority list. For the common case, sort_by_key with a tuple key sorts lexicographically over the tuple (mirroring the derived struct order), and wrapping a field in Reverse flips just that field's direction, usually cleaner than a hand-written then_with chain.

Choosing a Sort

The throughline: reach for the least powerful tool that expresses the order, sort_by_key with a tuple handles most multi-field cases, and sort_by with then_with is the escape hatch for the rest. And remember floats need total_cmp, never partial_cmp().unwrap().

Key Takeaways

• Use sort() for natural order, sort_by_key to sort by an extracted value, and sort_by only for comparisons too complex for a single key. Prefer sort_by_key when both fit, it's harder to get wrong.
• sort_by_key recomputes the key on every comparison; use sort_by_cached_key when key extraction is expensive.
• sort is stable (equal elements keep input order) but allocates; sort_unstable is faster with no allocation. Default to sort_unstable unless tie order matters.
• #[derive(PartialOrd, Ord)] sorts lexicographically by field declaration order, so field order sets sort priority; Ord needs Eq, so derive all four.
• Floats are PartialOrd but not Ord because of NaN; sort them with f64::total_cmp, never partial_cmp().unwrap() (which panics on NaN).
• Compose multi-key sorts with a tuple key plus Reverse for descending fields, or sort_by + then_with chains as tiebreakers evaluated only on Equal.