Rust Sort and Custom Comparators: The Coding Interview Reference

Six sort methods. Most engineers know two. That's fine until you're in an interview, you've got a Vec<f64>, and the compiler tells you, politely but firmly and with absolutely zero flexibility, that f64 doesn't implement Ord. At that point you either know total_cmp or you start sweating.

Default to sort_unstable and sort_unstable_by for almost everything, use total_cmp for floats, and switch to sort_by the moment sort_by_key refuses to compile because it can't borrow your struct fields.

Six Methods. One Right Default.

Method	Stable	Custom logic	Key computed
sort()	Yes	No	N/A
sort_unstable()	No	No	N/A
sort_by(|a, b| ...)	Yes	Ordering closure	N/A
sort_unstable_by(|a, b| ...)	No	Ordering closure	N/A
sort_by_key(|x| key)	Yes	Extracted key	O(n log n) times
sort_by_cached_key(|x| key)	Yes	Extracted key	Once per element
sort_unstable_by_key(|x| key)	No	Extracted key	O(n log n) times

Yes, there are seven rows. One of them is sort_by_cached_key, which exists because someone got tired of their key function running O(n log n) times for no reason.

Stable sort matters when equal elements have meaningful identities you need to preserve. That requirement is rare in LeetCode-style problems. Skip the ~40% performance cost unless you have a concrete reason.

Since Rust 1.81, sort_unstable uses ipnsort (derived from pdqsort) and sort uses driftsort. Both are significant upgrades. The unstable variant is roughly 40% faster on random integer arrays.

When you're unsure which to pick, here's the full decision tree:

Comparators Return Ordering. Not a Boolean.

Every sort_by closure returns std::cmp::Ordering: Less, Equal, or Greater. If the closure says the first argument is Less, that element ends up earlier in the output. This is the part that trips up people coming from JavaScript, where comparators return a number and sorting is an adventure.

// ascending
v.sort_unstable_by(|a, b| a.cmp(b));

// descending: swap the arguments
v.sort_unstable_by(|a, b| b.cmp(a));

cmp works on any type implementing Ord: integers, characters, strings. The trouble starts with floats.

You can chain comparators with .then_with(|| ...) or flip any Ordering with .reverse(). More on both shortly.

f64 Has No Ord. Your Code Won't Compile. The Compiler Is Correct.

This is the most common Rust sorting surprise in an interview. f64 implements PartialOrd but not Ord, because IEEE 754 has NaN, and NaN != NaN violates the reflexivity that Ord demands. The compiler doesn't care that your data is "basically clean." There's no probably_no_NaN_sort.

let mut prices = vec![3.5_f64, 1.2, 4.8, 2.1];
prices.sort(); // error: the trait `Ord` is not implemented for `f64`

The correct idiom since Rust 1.62 is total_cmp:

prices.sort_unstable_by(|a, b| a.total_cmp(b));

total_cmp defines a total order over all float values, placing -NaN before -Infinity and +NaN after +Infinity. It never panics.

The older pattern is a.partial_cmp(b).unwrap(). It works for non-NaN inputs but panics the moment any NaN appears. Don't use it unless clean data is guaranteed and you want the panic to surface bugs. In an interview, it will surface bugs.

Descending Sort: Reverse<T> Composes. Swapping Arguments Doesn't.

Swapping a and b in sort_by works for a single-key descending sort. But std::cmp::Reverse<T> is cleaner inside sort_by_key or when building compound keys.

use std::cmp::Reverse;

let mut nums = vec![3, 1, 4, 1, 5, 9, 2, 6];
nums.sort_unstable_by_key(|&x| Reverse(x));
// [9, 6, 5, 4, 3, 2, 1, 1]

Reverse<T> is a newtype that flips Ord, so you can compose it freely inside tuple keys without writing a closure.

Sorting Structs: Derive or Write a Closure

Approach 1: Derive Ord if the default field order works.

#[derive(Eq, PartialEq, Ord, PartialOrd)]
struct Task {
    priority: u32, // primary sort key
    name: String,  // secondary sort key
}

let mut tasks: Vec<Task> = vec![...];
tasks.sort_unstable();

Field declaration order is your sort order. Derived Ord compares fields top-to-bottom. If you need priority ascending but name descending, derive won't cut it. If any field is f64, derive won't compile either.

Approach 2: Write a sort_by closure for full control.

// score descending, then name ascending
tasks.sort_unstable_by(|a, b| {
    b.score.cmp(&a.score)
           .then_with(|| a.name.cmp(&b.name))
});

Ordering::then_with chains comparisons and only evaluates the second when the first returns Equal. Use then_with (lazy, takes a closure) over then (eager, always evaluates both) when the tiebreaker involves any real work.

Tuple Keys for Multi-Key Sorting

When all sub-keys point the same direction, a tuple key is the most concise option:

tasks.sort_unstable_by_key(|t| (t.priority, t.score));
// primary: priority ascending; secondary: score ascending

Mix directions with Reverse:

// priority ascending, score descending
tasks.sort_unstable_by_key(|t| (t.priority, Reverse(t.score)));

Tuple Ord is lexicographic. This behaves exactly like the chained then_with approach and reads more clearly when the logic is simple.

sort_by_key Can't Return Borrowed Data

This is the borrow-checker trap that catches engineers who reach for sort_by_key reflexively. The borrow checker doesn't always know what's happening either.

let mut words = vec!["banana", "apple", "cherry"];

// Fine: key is an owned String
words.sort_by_key(|s| s.to_uppercase());

// Error: sort_by_key can't return a reference into the slice
words.sort_by_key(|s| s.as_str());

sort_by_key requires the key type not to borrow from the element, a lifetime restriction baked into the method signature. When you need to sort by a borrowed field, use sort_by directly:

structs.sort_unstable_by(|a, b| a.name.cmp(&b.name));

sort_by takes a closure over two references and returns Ordering, so borrows from both arguments are fine. This is the go-to whenever sort_by_key refuses to compile.

When even the borrow checker contradicts itself, sort_by is the only way out.

Five Traps That Cost You Interview Time

1. The subtraction comparator (a C/Java habit)

In C or Java, a - b is a common comparator shortcut. In Rust, this will either panic loudly or silently produce wrong results. Both outcomes are worse than using a.cmp(b).

// Wrong: panics on usize underflow in debug, silent wrap on i32 overflow
v.sort_by(|a, b| (a - b).cmp(&0));

// Right
v.sort_by(|a, b| a.cmp(b));

With usize, subtraction underflows when a < b, panicking in debug mode. With signed integers, large values overflow and flip the comparison silently. a.cmp(&b) is always correct and just as fast. There is no reason to use subtraction. There never was.

2. f64 doesn't compile with sort()

Covered above. Write sort_unstable_by(|a, b| a.total_cmp(b)) once, move on. The alternative is spending three minutes staring at a compiler error while your interviewer watches.

3. sort_by_key calls the key function O(n log n) times

If the key computation is expensive (parsing, hashing, a syscall), use sort_by_cached_key instead. It calls the closure once per element.

v.sort_by_cached_key(|x| expensive_key(x)); // called n times, not n log n

For cheap keys like integer field access, sort_by_key is fine.

4. Assuming you need stable sort

Most interview problems don't care about stability. You're paying ~40% overhead for nothing. sort_unstable is the right default. The stable sort deep-dive covers the narrow cases where stability actually matters.

5. Derive field order surprises

When you #[derive(Ord)], fields are compared in declaration order. Moving a field to fix an unrelated bug silently changes your sort behavior. If sort order is critical, name fields in sort-priority order, or skip derive and write an explicit comparator you can read later. Your future self will be confused enough already.

Quantum bogosort has O(1) expected time. The subtraction comparator has O(panic) expected time. Choose carefully.

Quick Reference

The patterns you'll reach for most often:

// integers ascending
v.sort_unstable();

// integers descending
v.sort_unstable_by(|a, b| b.cmp(a));
v.sort_unstable_by_key(|&x| Reverse(x)); // same result

// f64 ascending
v.sort_unstable_by(|a, b| a.total_cmp(b));

// f64 descending
v.sort_unstable_by(|a, b| b.total_cmp(a));

// struct by one integer field ascending
v.sort_unstable_by_key(|x| x.score);

// struct by one integer field descending
v.sort_unstable_by_key(|x| Reverse(x.score));

// struct by borrowed string field (sort_by_key won't borrow)
v.sort_unstable_by(|a, b| a.name.cmp(&b.name));

// multi-key: primary ascending, secondary descending
v.sort_unstable_by_key(|x| (x.primary, Reverse(x.secondary)));

// chained comparator
v.sort_unstable_by(|a, b| {
    a.primary.cmp(&b.primary)
             .then_with(|| b.secondary.cmp(&a.secondary))
});

Practice the Explanation, Not Just the Code

Writing a sort_unstable_by comparator at your desk is easy. Explaining out loud why you picked it over sort_by_key, why total_cmp instead of partial_cmp().unwrap(), and what happens to NaN values while an interviewer is watching is a different skill. Rust interviews score the narration alongside the code.

SpaceComplexity runs voice-based mock interviews that score your reasoning alongside your solution. If Rust is your interview language, practice these explanations out loud before you sit down for the real thing.

For more on Rust in interviews, see Rust for Coding Interviews. If you're still choosing a language, Best Language for Coding Interviews covers the tradeoffs honestly.

Further Reading

• slice::sort (doc.rust-lang.org)
• std::cmp::Reverse (doc.rust-lang.org)
• f64::total_cmp (doc.rust-lang.org)
• Pattern-defeating quicksort paper (arxiv.org)
• Driftsort introduction (github.com)