Sorting vectors in Rust
You just scraped a list of prices from a website, but they came back in random order. Or your game engine generated a bunch of entities, and the renderer needs them sorted by Z-depth before drawing. You have a Vec, and you need it ordered. In Python, you'd call .sort() or sorted(). In Rust, you do too, but the compiler has opinions about mutability and what "order" actually means.
Rust's sorting methods work in place. They rearrange the elements inside the existing vector. They don't create a new vector and return it. Think of sorting a deck of cards in your hand. You don't deal out a fresh deck in the right order; you shuffle the cards you already hold until they're sorted. This saves memory and allocation time. The trade-off is that you need a mutable reference to the vector. If you can't mutate it, you have to clone it first, which costs performance.
Minimal example
Start with the basics. If your vector holds types that implement Ord, like integers or strings, you can call sort directly.
/// Sorts a vector of integers in ascending order.
fn main() {
// `mut` is required because sort modifies the vector in place.
let mut scores = vec![42, 11, 99, 7];
// `sort` uses the default ordering for the element type.
// For integers, this is ascending numerical order.
scores.sort();
// The vector is now rearranged.
assert_eq!(scores, vec![7, 11, 42, 99]);
}
Convention aside: If you're sorting primitive types like i32 or u8, reach for sort_unstable instead of sort. It's faster because it doesn't preserve the relative order of equal elements, which allows the algorithm to skip certain checks. For primitives, stability rarely matters, and the speed win is real.
/// Sorts primitives faster by skipping stability checks.
fn main() {
let mut ids = vec![5, 2, 9, 2, 1];
// `sort_unstable` is preferred for primitives.
// It uses a faster algorithm when equal elements can be reordered.
ids.sort_unstable();
// Result: [1, 2, 2, 5, 9].
// The two `2`s might swap positions relative to each other.
assert_eq!(ids, vec![1, 2, 2, 5, 9]);
}
Use sort_unstable for primitives. It's the idiomatic choice for numbers, booleans, and enums where stability provides no value.
How the algorithm works
Under the hood, Rust uses a hybrid sorting algorithm. For stable sorting, it uses Timsort, which is excellent for data that's already partially sorted. Timsort detects runs of ordered data and merges them efficiently. For unstable sorting, it uses a variant of Quicksort that guarantees O(n log n) worst-case performance.
Both algorithms run in O(n log n) time on average. The compiler inlines the comparison logic when you use sort_by, so the closure overhead vanishes. You're paying for the comparisons and the swaps, nothing more.
Stability matters when you have equal elements and you care about their original relative order. Imagine sorting a list of transactions by date. If two transactions happened on the same day, a stable sort keeps them in the order they were inserted. An unstable sort might swap them. Stability costs a bit of performance because the algorithm has to do extra work to preserve order. If you don't need it, drop the cost with sort_unstable.
Sorting structs and custom types
Real data isn't just numbers. You usually have structs. Say you're building a file manager and need to sort files by size, then by name.
/// Represents a file entry with metadata.
struct FileEntry {
name: String,
size_bytes: u64,
}
fn main() {
let mut files = vec![
FileEntry { name: "readme.md".into(), size_bytes: 1024 },
FileEntry { name: "image.png".into(), size_bytes: 50000 },
FileEntry { name: "script.sh".into(), size_bytes: 1024 },
];
// Sort by size first. If sizes are equal, sort by name.
// `sort_by` takes a closure that returns an `Ordering`.
files.sort_by(|a, b| {
// Compare sizes first.
match a.size_bytes.cmp(&b.size_bytes) {
// If sizes differ, use that result.
std::cmp::Ordering::Equal => {
// Sizes are equal, fall back to name comparison.
a.name.cmp(&b.name)
}
// Sizes differ, return the size comparison.
other => other,
}
});
// Result: script.sh (1024), readme.md (1024), image.png (50000).
// Note: script comes before readme alphabetically.
}
Convention aside: If you only need to sort by one field, use sort_by_key. It's cleaner and often faster because the key is computed once per element, not repeatedly during comparisons. files.sort_by_key(|f| f.size_bytes) is the idiomatic choice for single-key sorts.
/// Sorts files by size using a single key.
fn main() {
let mut files = vec![
FileEntry { name: "readme.md".into(), size_bytes: 1024 },
FileEntry { name: "image.png".into(), size_bytes: 50000 },
];
// `sort_by_key` computes the key once per element.
// This avoids redundant calculations inside the comparison loop.
files.sort_by_key(|f| f.size_bytes);
// Result: readme.md, image.png.
}
If the key computation is expensive, sort_by_key is your friend. It computes the key once, not every time two elements are compared.
Pitfalls and compiler errors
Sorting trips up developers in predictable ways. The compiler catches most mistakes, but you need to know what to look for.
If you forget mut, the compiler rejects you with E0596 (cannot borrow as mutable). Sorting requires writing back to the vector. You can't sort an immutable binding. Add mut to the binding, not the variable name.
// This fails to compile.
let scores = vec![3, 1, 2];
scores.sort(); // Error E0596: cannot borrow as mutable
You can't call sort() on a vector of custom structs unless the struct implements Ord. The compiler will hit you with E0277 (trait bound not satisfied). Derive the trait with #[derive(PartialEq, Eq, PartialOrd, Ord)] or use sort_by to provide the logic manually.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Point {
x: i32,
y: i32,
}
fn main() {
let mut points = vec![Point { x: 2, y: 1 }, Point { x: 1, y: 2 }];
// Now `sort` works because Point implements Ord.
points.sort();
}
Sorting floats is tricky. NaN breaks the total order required by Ord. If your vector contains NaN, sort will panic. Use sort_by with a custom comparator that handles NaN, or filter them out first.
fn main() {
let mut values = vec![1.5, f64::NAN, 0.5, 2.0];
// `sort` would panic here due to NaN.
// Use `sort_by` to handle NaN explicitly.
values.sort_by(|a, b| {
a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Greater)
});
// NaN is pushed to the end.
}
Python developers often look for a sorted() function that returns a new vector. Rust doesn't have one in the standard library. If you need a new sorted vector without mutating the original, clone it first. Or use the itertools crate, which provides a sorted() adapter.
fn main() {
let original = vec![3, 1, 2];
// Clone and sort to get a new vector.
let mut sorted = original.clone();
sorted.sort();
// `original` is unchanged.
assert_eq!(original, vec![3, 1, 2]);
}
Derive Ord early. It saves you from writing boilerplate comparators later and makes your types usable in maps and sets.
Decision matrix
Use sort when you have a vector of types that implement Ord and you need a stable sort. Stability matters when equal elements must keep their original relative order, like sorting a list of transactions by date where the original insertion order should be preserved for ties.
Use sort_unstable when you're sorting primitive types or when the relative order of equal elements doesn't matter. It's faster because it skips stability checks, and for numbers, strings, or enums, stability is almost never required.
Use sort_by_key when you need to sort by a single derived property. It computes the key once per element and caches it, avoiding redundant calculations inside the comparison loop. This is the go-to for sorting structs by one field.
Use sort_by when you need complex multi-field logic or custom comparison rules. It gives you full control over the Ordering result, letting you chain comparisons or handle edge cases like NaN in floats.
Use sort_unstable_by_key when you have a single key and stability isn't needed. It combines the speed of unstable sorting with the caching of key computation, making it the fastest option for single-key sorts on large datasets.
Sort in place. Cloning just to sort is a performance tax you rarely need to pay.