Sorting

#108 Apr 2026
iterator std sorting

108. Iterator::max_by_key — Find the Biggest Without Sorting the Whole Thing

Need the longest string in a Vec? Don’t sort the whole list to grab the last element — max_by_key walks once, allocates nothing, and returns it directly.

The wasteful way

You want the longest word from a list. The first instinct is often to sort and pick:

1
2
3
4
5
6
7

let mut words = vec!["fig", "apple", "kiwi", "blackberry", "pear"];

// Sort the full vec by length, then grab the last element.
words.sort_by_key(|w| w.len());
let longest = words.last().unwrap();

assert_eq!(*longest, "blackberry");

That’s O(n log n) work — and a side effect, since your Vec is now reordered — just to answer “which one is biggest?”.

Enter max_by_key

max_by_key walks the iterator once, tracks the running maximum, and hands you the element it picked:

1
2
3
4
5

let words = vec!["fig", "apple", "kiwi", "blackberry", "pear"];

let longest = words.iter().max_by_key(|w| w.len()).unwrap();

assert_eq!(*longest, "blackberry");

O(n), no allocation, no mutation. The original Vec is untouched and you get a &&str back without cloning anything.

Same energy: min_by_key

The mirror method is just as useful — find the shortest word in one pass:

1
2
3
4
5

let words = vec!["fig", "apple", "kiwi", "blackberry", "pear"];

let shortest = words.iter().min_by_key(|w| w.len()).unwrap();

assert_eq!(*shortest, "fig");

Picking by computed value

The closure can do real work — compute distance, score, age — anything that returns something Ord:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct Player { name: &'static str, score: u32 }

let roster = [
    Player { name: "Ferris", score: 80 },
    Player { name: "Corro",  score: 95 },
    Player { name: "Crusty", score: 60 },
];

let top = roster.iter().max_by_key(|p| p.score).unwrap();

assert_eq!(top.name, "Corro");

No need to sort, no need to implement Ord on the struct — just point at the field that decides.

Tiebreaks: last one wins

When two elements share the same key, max_by_key returns the last one and min_by_key returns the first:

1
2
3
4
5
6
7

let v = vec![(1, 'a'), (3, 'b'), (3, 'c'), (2, 'd')];

let max = v.iter().max_by_key(|(k, _)| *k).unwrap();
let min = v.iter().min_by_key(|(k, _)| *k).unwrap();

assert_eq!(*max, (3, 'c')); // last 3
assert_eq!(*min, (1, 'a')); // first 1

Worth knowing if your data has duplicates — pick the iteration direction so the right element wins.

When to reach for it

If you catch yourself sorting and then grabbing first(), last(), or [0], stop. min_by_key and max_by_key are the targeted tools: one pass, zero allocations, and the result type is exactly the element you wanted.

#101 Apr 2026
std sorting floats

101. f64::total_cmp — Sort Floats Without the NaN Panic

Tried v.sort() on a Vec<f64> and hit the trait Ord is not implemented for f64? Then reached for .sort_by(|a, b| a.partial_cmp(b).unwrap()) and now a stray NaN is about to panic your service at 3am? f64::total_cmp is the one-liner that makes both problems disappear.

Why f64 doesn’t implement Ord

Floats form a partial order because NaN is not equal to anything — not even itself. So f64: PartialOrd but not Ord, which means sort() flat out refuses to compile:

1
2

let mut temps: Vec<f64> = vec![21.5, 18.0, 23.0, 19.5];
// temps.sort(); // ❌ the trait `Ord` is not implemented for `f64`

The classic workaround is partial_cmp().unwrap():

1
2
3
4

let mut temps: Vec<f64> = vec![21.5, 18.0, 23.0, 19.5];
temps.sort_by(|a, b| a.partial_cmp(b).unwrap());

assert_eq!(temps, [18.0, 19.5, 21.5, 23.0]);

Works — until a NaN sneaks in. Then partial_cmp returns None, the unwrap fires, and your sort becomes a panic.

Enter total_cmp

f64::total_cmp implements the IEEE 754 totalOrder predicate: a real total ordering on every f64 bit pattern, including all the NaNs. It returns Ordering directly — no Option, no panic:

1
2
3
4

let mut temps: Vec<f64> = vec![21.5, 18.0, 23.0, 19.5];
temps.sort_by(f64::total_cmp);

assert_eq!(temps, [18.0, 19.5, 21.5, 23.0]);

Same result for well-behaved input, but now NaN won’t take the process down:

1
2
3
4
5
6
7
8
9

let mut values: Vec<f64> = vec![3.0, f64::NAN, 1.0, f64::NEG_INFINITY, 2.0];
values.sort_by(f64::total_cmp);

// Finite values in order, -∞ at the front, NaN at the back.
assert_eq!(values[0], f64::NEG_INFINITY);
assert_eq!(values[1], 1.0);
assert_eq!(values[2], 2.0);
assert_eq!(values[3], 3.0);
assert!(values[4].is_nan());

min and max too

partial_cmp poisons more than just sort. Any time you reach for iter().max_by(|a, b| a.partial_cmp(b).unwrap()), you’ve written the same latent panic. total_cmp fits there too:

1
2
3
4
5
6
7

let readings = [3.2_f64, 1.4, 4.8, 2.1];

let peak = readings.iter().copied().max_by(f64::total_cmp).unwrap();
let low  = readings.iter().copied().min_by(f64::total_cmp).unwrap();

assert_eq!(peak, 4.8);
assert_eq!(low, 1.4);

Sorting structs by a float field

Because total_cmp takes two &f64s and returns Ordering, it slots straight into sort_by:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct Trade { symbol: &'static str, price: f64 }

let mut book = vec![
    Trade { symbol: "AAPL", price: 172.40 },
    Trade { symbol: "NVDA", price: 915.10 },
    Trade { symbol: "MSFT", price: 419.80 },
];

book.sort_by(|a, b| a.price.total_cmp(&b.price));

assert_eq!(book[0].symbol, "AAPL");
assert_eq!(book[2].symbol, "NVDA");

When to reach for it

Any time you’re about to type partial_cmp(...).unwrap() for a float, stop and use total_cmp instead. f32::total_cmp works the same way. Available since Rust 1.62 — the fix has been hiding in plain sight for years.

#100 Apr 2026
std sorting collections

100. std::cmp::Reverse — Sort Descending Without Writing a Closure

Want to sort a Vec in descending order? The old trick is v.sort_by(|a, b| b.cmp(a)), and every time you write it you flip a and b and pray you got it right. std::cmp::Reverse is a one-word replacement.

The closure swap trick

To sort descending, you reverse the comparison. The closure is short but easy to mess up:

1
2
3
4

let mut scores = vec![30, 10, 50, 20, 40];
scores.sort_by(|a, b| b.cmp(a));

assert_eq!(scores, [50, 40, 30, 20, 10]);

Swap the a and b and you silently get ascending order again. Not a bug the compiler can help with.

Enter Reverse

std::cmp::Reverse<T> is a tuple wrapper whose Ord impl is the reverse of T’s. Hand it to sort_by_key and you’re done:

1
2
3
4
5
6

use std::cmp::Reverse;

let mut scores = vec![30, 10, 50, 20, 40];
scores.sort_by_key(|&s| Reverse(s));

assert_eq!(scores, [50, 40, 30, 20, 10]);

No chance of flipping the comparison the wrong way — the intent is right there in the name.

Sorting by a field, descending

It really shines when you’re sorting structs by a specific field:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

use std::cmp::Reverse;

#[derive(Debug)]
struct Player {
    name: &'static str,
    score: u32,
}

let mut roster = vec![
    Player { name: "Ferris", score: 42 },
    Player { name: "Corro",  score: 88 },
    Player { name: "Rusty",  score: 65 },
];

roster.sort_by_key(|p| Reverse(p.score));

assert_eq!(roster[0].name, "Corro");
assert_eq!(roster[1].name, "Rusty");
assert_eq!(roster[2].name, "Ferris");

Mixing ascending and descending

Sort by one field ascending and another descending? Pack them in a tuple — Reverse composes cleanly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use std::cmp::Reverse;

let mut items = vec![
    ("apple",  3),
    ("banana", 1),
    ("apple",  1),
    ("banana", 3),
];

// Name ascending, then count descending.
items.sort_by_key(|&(name, count)| (name, Reverse(count)));

assert_eq!(items, [
    ("apple",  3),
    ("apple",  1),
    ("banana", 3),
    ("banana", 1),
]);

It works anywhere Ord does

Because Reverse<T> is an Ord type, you can use it with BinaryHeap to turn a max-heap into a min-heap, or with BTreeSet to iterate in reverse order — no extra wrapper types needed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

use std::cmp::Reverse;
use std::collections::BinaryHeap;

// BinaryHeap is max-heap by default. Wrap in Reverse for min-heap behaviour.
let mut heap = BinaryHeap::new();
heap.push(Reverse(3));
heap.push(Reverse(1));
heap.push(Reverse(2));

assert_eq!(heap.pop(), Some(Reverse(1)));
assert_eq!(heap.pop(), Some(Reverse(2)));
assert_eq!(heap.pop(), Some(Reverse(3)));

When to reach for it

Any time you’d write b.cmp(a) — reach for Reverse instead. The code reads top-to-bottom, the intent is obvious, and there’s no comparator to accidentally flip.

#098 Apr 2026
sorting performance slice std

98. sort_by_cached_key — Stop Recomputing Expensive Sort Keys

sort_by_key sounds like it computes the key once per element. It doesn’t — it calls your closure at every comparison, so an n-element sort can pay for that key O(n log n) times. If the key is expensive, sort_by_cached_key is the fix you’ve been looking for.

The trap

The signature reads nicely: “sort by this key.” The implementation, less so — the closure fires on every comparison, not once per element:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

use std::cell::Cell;

let mut items = vec!["banana", "fig", "apple", "cherry", "date"];
let calls = Cell::new(0);

items.sort_by_key(|s| {
    calls.set(calls.get() + 1);
    // Pretend this is a heavy computation: allocating, hashing,
    // parsing, calling a regex, opening a file, etc.
    s.to_string()
});

// 5 elements, but the key ran way more than 5 times.
assert!(calls.get() > items.len());
assert_eq!(items, ["apple", "banana", "cherry", "date", "fig"]);

For identity keys that cost a pointer-deref, nobody cares. For anything that allocates — .to_string(), .to_lowercase(), format!(...), a regex capture, a trimmed-and-lowered filename — the cost compounds quickly. I’ve seen a profile where 80% of total runtime was the key closure being called 40,000 times to sort 2,000 items.

The fix

slice::sort_by_cached_key runs your closure exactly once per element, stashes the results in a scratch buffer, then sorts against the cache. This is the Schwartzian transform, wrapped up in a method call:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

use std::cell::Cell;

let mut items = vec!["banana", "fig", "apple", "cherry", "date"];
let calls = Cell::new(0);

items.sort_by_cached_key(|s| {
    calls.set(calls.get() + 1);
    s.to_string()
});

// Exactly one call per element — no matter how big the slice is.
assert_eq!(calls.get(), items.len());
assert_eq!(items, ["apple", "banana", "cherry", "date", "fig"]);

Same result, linear key-function calls. The memory trade is a Vec<(K, usize)> the size of the slice — cheap next to the cost of re-running an allocating closure on every compare.

When to reach for which

The rule is about where your time goes, not how fancy the key looks:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

let mut nums = vec![5u32, 2, 8, 1, 9, 3];

// Trivial key: sort_by_key is fine (and avoids the scratch alloc).
nums.sort_by_key(|n| *n);
assert_eq!(nums, [1, 2, 3, 5, 8, 9]);

// Expensive key: sort_by_cached_key wins.
let mut files = vec!["Cargo.TOML", "src/MAIN.rs", "README.md", "build.RS"];
files.sort_by_cached_key(|path| path.to_lowercase());
assert_eq!(files, ["build.RS", "Cargo.TOML", "README.md", "src/MAIN.rs"]);

Use sort_by_key for cheap, Copy-ish keys. Use sort_by_cached_key the moment your closure allocates, hashes, parses, or otherwise does real work — it’s the difference between O(n log n) and O(n) calls to that closure.

#075 Apr 2026
slices sorting algorithms performance

75. select_nth_unstable — Find the Kth Element Without Sorting

You’re sorting an entire Vec just to grab the median or the top 3 elements. select_nth_unstable does it in O(n) — no full sort required.

The classic approach: sort everything, then index:

1
2
3
4

let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
scores.sort();
let median = scores[scores.len() / 2];
assert_eq!(median, 73);

That’s O(n log n) to answer an O(n) question. select_nth_unstable uses a partial-sort algorithm (quickselect) to put the element at a given index into its final sorted position — everything before it is smaller or equal, everything after is greater or equal:

1
2
3
4

let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
let mid = scores.len() / 2;
scores.select_nth_unstable(mid);
assert_eq!(scores[mid], 73);

The method returns three mutable slices — elements below, the pivot element, and elements above — so you can work with each partition directly:

1
2
3
4
5
6
7

let mut data = vec![10, 80, 30, 90, 50, 70, 20];
let (lower, median, upper) = data.select_nth_unstable(3);
// lower contains 3 elements all <= *median
// upper contains 3 elements all >= *median
assert_eq!(*median, 50);
assert!(lower.iter().all(|&x| x <= 50));
assert!(upper.iter().all(|&x| x >= 50));

Need the top 3 scores without sorting the full list? Select the boundary, then sort only the small tail:

1
2
3
4
5
6

let mut scores = vec![82, 45, 99, 67, 73, 91, 55];
let k = scores.len() - 3;
scores.select_nth_unstable(k);
let top_3 = &mut scores[k..];
top_3.sort_unstable(); // sort only 3 elements, not all 7
assert_eq!(top_3, &[82, 91, 99]);

Custom ordering works too. Find the median by absolute value:

1
2
3
4

let mut vals = vec![-20, 5, -10, 15, -3, 8, 1];
let mid = vals.len() / 2;
vals.select_nth_unstable_by_key(mid, |v| v.abs());
assert_eq!(vals[mid].abs(), 8);

The “unstable” in the name means equal elements might be reordered (like sort_unstable) — it doesn’t mean the API is experimental. This is stable since Rust 1.49, available on any [T] where T: Ord.

#074 Apr 2026
slices sorting iterators

74. slice::is_sorted — Ask the Slice if It's Already Sorted

You’ve written windows(2).all(|w| w[0] <= w[1]) one too many times. The is_sorted family of methods says what you actually mean — in one call.

Checking whether data is already in order used to mean rolling your own predicate:

1
2
3
4
5

let data = vec![1, 3, 5, 7, 9];

// The old way — correct but noisy:
let sorted = data.windows(2).all(|w| w[0] <= w[1]);
assert!(sorted);

It works, but you have to remember windows(2), get the comparison direction right, and hope the next reader recognizes the pattern.

Now there’s a method that does exactly this:

1
2
3
4
5

let data = vec![1, 3, 5, 7, 9];
assert!(data.is_sorted());

let messy = vec![1, 9, 3, 7, 5];
assert!(!messy.is_sorted());

Empty slices and single-element slices are considered sorted — no edge-case surprises:

1
2
3

let empty: Vec<i32> = vec![];
assert!(empty.is_sorted());
assert!(vec![42].is_sorted());

Need a custom comparator? is_sorted_by takes a closure over pairs of references and returns bool:

1
2
3
4

// Check if sorted by absolute value
let vals: Vec<i32> = vec![-1, 2, -3, 4];
let sorted_by_abs = vals.is_sorted_by(|a, b| a.abs() <= b.abs());
assert!(sorted_by_abs);

And is_sorted_by_key extracts a key first — perfect for structs:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct Task {
    priority: u8,
    name: &'static str,
}

let tasks = vec![
    Task { priority: 1, name: "urgent" },
    Task { priority: 3, name: "normal" },
    Task { priority: 5, name: "backlog" },
];

assert!(tasks.is_sorted_by_key(|t| t.priority));

A practical use: skip sorting when the data is already ordered:

1
2
3
4
5

let mut data = vec![1, 2, 3, 4, 5];
if !data.is_sorted() {
    data.sort();
}
// Avoids the O(n log n) sort when data is already O(n)-verified sorted

Available on slices and by extension on Vec, arrays, and anything that derefs to [T]. Stabilized in Rust 1.82 — no crate needed.