247. sort_unstable — Skip the Allocation When Ties Don't Matter

.sort() pays for a guarantee you usually don’t need: it allocates a scratch buffer to keep equal elements in their original order. .sort_unstable() sorts in place — no allocation, and typically faster.

What “stable” actually buys you

A stable sort preserves the relative order of elements that compare equal. To do that, slice::sort allocates temporary storage proportional to the slice length. slice::sort_unstable works entirely in place and is generally the faster of the two — the docs themselves suggest preferring it when stability isn’t required:

1
2
3

let mut nums = [5, 3, 9, 1, 3];
nums.sort_unstable();
assert_eq!(nums, [1, 3, 3, 5, 9]);

For integers, floats-via-total_cmp, or any type where two equal elements are indistinguishable, stability buys you nothing — there is no observable “original order” among identical values. That’s most sorts you’ll ever write.

When you actually need .sort()

Stability matters when elements carry more data than the sort key, and the order of ties is meaningful. Classic case: re-sorting an already-sorted list by a second criterion:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Already sorted by name.
let mut employees = vec![
    ("alice", 2), ("bob", 1), ("carol", 2),
];

// Stable sort by department: names stay
// alphabetical within each department.
employees.sort_by_key(|&(_, dept)| dept);
assert_eq!(employees, [
    ("bob", 1), ("alice", 2), ("carol", 2),
]);

With sort_unstable_by_key, alice and carol (both dept 2) could end up in either order — the assert above would be a coin flip.

The unstable variants

Everything has an unstable twin: sort_unstable, sort_unstable_by, and sort_unstable_by_key:

1
2
3

let mut words = vec!["hello", "hi", "hey"];
words.sort_unstable_by_key(|w| w.len());
assert_eq!(words, ["hi", "hey", "hello"]);

Note one asymmetry: sort_by_key with an expensive key function has a cached cousin (sort_by_cached_key, bite 98), but there’s no sort_unstable_by_cached_key — caching needs the same kind of scratch allocation that unstable sorting exists to avoid.

Rule of thumb: reach for sort_unstable by default; upgrade to sort only when a tie-breaking order among equal elements is part of your program’s meaning.