Sorting: sort vs sort_unstable vs sort_by_cached_key

The folklore about sorting in Rust is wrong in one direction and enormously right in another, and no clippy lint tells you about the one that matters.

The advice everyone repeats

Always use sort_unstable, it is faster.

Measured, sorting a million i64s on this toolchain:

4.5%. Real, but nowhere near what “always” implies. The genuine difference is that sort allocates a scratch buffer and sort_unstable does not, which matters in a no_std or allocation-budgeted context far more than the wall clock does.

The advice nobody repeats

Sorting 200 000 rows by a key that has to be computed:

11.5×. Here is why, and it is the single most useful fact in this item:

sort_by_key calls your key function O(n log n) times, not n times.

It calls it at every comparison. For 200 000 elements that is roughly 3.5 million calls to produce 200 000 distinct keys. If the key is |r| r.id that is free and you should not care. If the key allocates — a to_lowercase, a to_string, a collect — you have just multiplied the expensive part by fourteen.

sort_by_cached_key computes each key exactly once, stores them in a side table, sorts the table, and applies the permutation. The documentation mentions the call count in passing and almost nobody reads it.

The lesson is that key cost, not stability, dominates.

And the counter-lesson

sort_by_cached_key allocates that side table. For a cheap key it is pure overhead — you pay an allocation and an extra indirection to avoid recomputing something that costs nothing. So reaching for it reflexively is its own mistake, and this problem checks that you do not.

What to write

pub struct Row { pub id: u32, pub name: String }

pub fn rank_records(rows: &[Row]) -> Vec<u32>
pub fn rank_by_len(rows: &[Row]) -> Vec<u32>

Both return the ids of every row, reordered.

• rank_records sorts by the expensive key — the row’s name lowercased and reversed — with ties broken by ascending id.
• rank_by_len sorts by the trivial key name.len(), again with ties broken by ascending id.

Ids are unique, so both orderings are total: stable and unstable sorts give exactly the same answer, and correctness cannot distinguish them. The allocation budgets can.

The two budgets

• rank_records: at most 3n + 64 allocations. The reference does about 2n + 3 — one to_lowercase and one collect per row, computed once each. sort_by_key with the same key does about 1 228 000 at n = 20 000, and fails by a factor of twenty.
• rank_by_len: at most 2 allocations, total. Building an index vector and collecting the answer is two. Adding sort_by_cached_key makes it three, and fails.

Three more things that will bite you

E0521. The obvious way to sort by a borrowed key — rows.sort_by_key(|r| &r.name) — does not compile: sort_by_key‘s key type cannot borrow from the element, because the closure’s return would have to outlive the borrow it came from. It is a notorious papercut and it is what pushes people into sort_by(|a, b| a.name.cmp(&b.name)), which is the correct workaround.

f64 has no Ord. sort_by_key and sort will not take it. The usual hack a.partial_cmp(&b).unwrap() panics on NaN. Since 1.62 the right answer is a.total_cmp(&b), which implements IEEE-754’s total ordering and never panics.

Since 1.81 the sorts may detect a broken comparator. If your Ord or comparison closure is not a strict weak ordering, the documented outcomes are “may panic” or “returns with the slice in an unspecified order” — both are legal, and which you get depends on the input. Verified: a comparator that always returns Less never panics up to n = 10 000, while a pseudo-random one panics from n = 40. Never write a test that asserts the panic. Write a correct comparator instead.

Related lints

unnecessary_sort_by (you wrote sort_by(|a, b| a.f().cmp(&b.f())) where sort_by_key(|x| x.f()) says it), stable_sort_primitive (pedantic — suggests sort_unstable on primitives), derive_ord_xor_partial_ord (correctness, denied by default — deriving one of Ord/PartialOrd while hand-writing the other is how you get a comparator that disagrees with itself), float_cmp.

Remember the grade is compile + tests + clippy -D warnings.