Rust Sorting & Searching

Sorting and searching are two jobs you’ll do in almost every program: ranking players by score, listing files by name, finding the cheapest product. Rust gives vectors and slices a set of built-in methods for both, so you rarely need to write your own algorithm.

Most of these methods take a closure that says how to compare two items. Once you get comfortable with that one idea, the rest of this page is just variations on it.

sort and sort_unstable

.sort() puts the items in ascending order (smallest first). It changes the vector in place, so the vector must be mut. Numbers sort by value; strings sort alphabetically.

fn main() {
    let mut scores = vec![42, 7, 99, 7, 15];
    scores.sort();
    println!("{:?}", scores);

    let mut names = vec!["Zoe", "adam", "Bob", "Ana"];
    names.sort_unstable();
    println!("{:?}", names);
}

Output:

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]

▶ Try it Yourself

Two things to notice:

• "adam" comes last. Strings compare by character code, and every uppercase letter comes before every lowercase one. Sort by name.to_lowercase() (shown below) if you want “dictionary” order.
• sort_unstable is usually a little faster and uses no extra memory. “Unstable” doesn’t mean buggy. It means items that compare as equal might swap places. For plain numbers or strings you can’t tell the difference, so it’s a fine default.

Reverse order

There are three common ways to sort from largest to smallest. They all give the same result here.

use std::cmp::Reverse;

fn main() {
    let mut a = vec![3, 8, 1, 5];
    a.sort();
    a.reverse();
    println!("{:?}", a);

    let mut b = vec![3, 8, 1, 5];
    b.sort_by(|x, y| y.cmp(x)); // y before x = descending
    println!("{:?}", b);

    let mut c = vec![3, 8, 1, 5];
    c.sort_by_key(|&n| Reverse(n));
    println!("{:?}", c);
}

Output:

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]

▶ Try it Yourself

x.cmp(y) returns an Ordering: Less, Equal, or Greater. sort_by uses it to decide which item goes first. Writing y.cmp(x) flips every decision, which flips the whole order. Reverse is a small wrapper from std::cmp that does the same flip for a key.

Sorting floats

Try .sort() on a vector of f64 and Rust refuses:

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0];
    prices.sort();
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
 --> src/main.rs:3:12
  |
3 |     prices.sort();
  |            ^^^^ the trait `Ord` is not implemented for `{float}`

Why? .sort() needs a total order (the Ord trait): for any two values, one must be less, equal, or greater. Floats have a special value, NaN (“not a number”), that isn’t less than, equal to, or greater than anything — not even itself. So floats only have PartialOrd, and .partial_cmp() returns an Option<Ordering> that is None for NaN.

You have two good fixes:

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0, 4.75];

    // If you're sure there's no NaN:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Works even with NaN (NaN goes to the end):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Output:

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]

▶ Try it Yourself

partial_cmp(...).unwrap() will panic if it meets a NaN. total_cmp never panics because it defines a fixed place for every float, including NaN. Prefer total_cmp unless you have a reason not to.

sort_by_key and sorting structs

sort_by_key takes a closure that picks what to sort by. That’s perfect for structs, where you choose a field.

#[derive(Debug)]
struct Product {
    name: String,
    price_cents: u32,
}

fn main() {
    let mut items = vec![
        Product { name: String::from("pen"), price_cents: 150 },
        Product { name: String::from("Notebook"), price_cents: 499 },
        Product { name: String::from("eraser"), price_cents: 75 },
    ];

    items.sort_by_key(|p| p.price_cents);
    for p in &items {
        println!("{} - {}", p.price_cents, p.name);
    }

    items.sort_by_key(|p| p.name.to_lowercase());
    let names: Vec<&str> = items.iter().map(|p| p.name.as_str()).collect();
    println!("{:?}", names);
}

Output:

75 - eraser
150 - pen
499 - Notebook
["eraser", "Notebook", "pen"]

▶ Try it Yourself

The key closure must return an owned value. p.price_cents is a u32, which is copied, so that’s fine. For a String field, you need a new String — that’s why the second sort uses to_lowercase(), which creates one. (See the mistakes section below.)

Sorting by several fields

A classic task: sort students by grade, highest first, and when two students have the same grade, sort them by name A to Z. Use sort_by with .then_with(). It only looks at the second comparison when the first one is a tie.

struct Student {
    name: String,
    grade: u32,
}

fn main() {
    let mut class = vec![
        Student { name: String::from("Liam"), grade: 88 },
        Student { name: String::from("Ava"), grade: 95 },
        Student { name: String::from("Noah"), grade: 88 },
        Student { name: String::from("Emma"), grade: 88 },
        Student { name: String::from("Mia"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // grade: high to low
            .then_with(|| a.name.cmp(&b.name)) // then name: A to Z
    });

    for s in &class {
        println!("{:>3}  {}", s.grade, s.name);
    }
}

Output:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ Try it Yourself

A shorter alternative is to return a tuple as the key. Tuples compare the first item, then the second, and so on:

class.sort_by_key(|s| (Reverse(s.grade), s.name.clone()));

This gives exactly the same order. It’s tidy, but it clones every name, so sort_by with then_with is the better habit for large lists.

Removing duplicates with dedup

.dedup() removes items that are equal to the one right before them. So it only removes all duplicates if the list is sorted first.

fn main() {
    let mut tags = vec!["rust", "web", "rust", "cli", "web", "web"];

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("dedup only:   {:?}", not_sorted);

    tags.sort();
    tags.dedup();
    println!("sort + dedup: {:?}", tags);
}

Output:

dedup only:   ["rust", "web", "rust", "cli", "web"]
sort + dedup: ["cli", "rust", "web"]

▶ Try it Yourself

Only the two "web" items that sat side by side were merged in the first try. Sort first, then dedup. If you need to keep the original order, use the HashSet trick from the HashSet page.

Searching: contains, position, max, min, binary_search

Here are the search tools you’ll use most:

• contains(&x) — is it there? Returns bool.
• iter().position(...) — where is the first match? Returns Option<usize>.
• iter().max() / iter().min() — largest and smallest, as an Option (it’s None for an empty list).
• iter().max_by_key(...) / min_by_key(...) — largest or smallest by some field.
• binary_search(&x) — very fast search, but only on a sorted list. Returns Ok(index) if found, or Err(index) saying where it would go.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("has 31? {}", temps.contains(&31));
    println!("first above 20 at: {:?}", temps.iter().position(|&t| t > 20));
    println!("max: {:?}, min: {:?}", temps.iter().max(), temps.iter().min());

    let players = vec![("ana", 340), ("ben", 515), ("chen", 220)];
    let best = players.iter().max_by_key(|(_, score)| *score).unwrap();
    println!("top player: {}", best.0);

    let mut sorted = vec![10, 20, 30, 40];
    println!("{:?}", sorted.binary_search(&30));
    let missing = sorted.binary_search(&25);
    println!("{:?}", missing);
    if let Err(pos) = missing {
        sorted.insert(pos, 25); // keeps the list sorted
    }
    println!("{:?}", sorted);
}

Output:

has 31? true
first above 20 at: Some(1)
max: Some(31), min: Some(12)
top player: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Try it Yourself

binary_search checks the middle item, throws away the half that can’t contain the value, and repeats. On a list of a million items that’s about 20 checks instead of up to a million. The Err(pos) answer is handy too: inserting at pos keeps the list sorted.

Caution

max() and min() need Ord, so they don’t work on floats either. Use max_by(|a, b| a.total_cmp(b)) instead — the same fix as for sorting.

Common mistakes

Returning a borrowed String field from sort_by_key. This looks natural but doesn’t compile:

students.sort_by_key(|s| s.name);

error[E0507]: cannot move out of `s.name` which is behind a shared reference
  --> src/main.rs:12:30
   |
12 |     students.sort_by_key(|s| s.name);
   |                              ^^^^^^ move occurs because `s.name` has type `String`, which does not implement the `Copy` trait

The closure only borrows each student, so it can’t give the String away. Either clone it (|s| s.name.clone()) or avoid the copy entirely with sort_by(|a, b| a.name.cmp(&b.name)).

Using binary_search on an unsorted list. It won’t crash, but the answer is meaningless: it may say a value is missing when it’s right there. Always sort first, or use contains / position instead.

Practice

1. Leaderboard

You have players as (name, score) tuples: ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Sort them by score, highest first, with ties sorted by name A to Z. Print only the top three. Hint: use sort_by with .then_with(), and a slice &players[..3] for the top three.

Show solution

fn main() {
    let mut players = vec![("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60)];

    players.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

    for (name, score) in &players[..3] {
        println!("{score} {name}");
    }
}

Output:

95 ana
88 dev
70 ben

▶ Try it Yourself

For a tuple, .0 is the name and .1 is the score. ben and chen both have 70, so the name breaks the tie and ben makes the top three.

2. The median price

Find the median (the middle value) of the prices 3.5, 1.25, 9.0, 4.75, 2.0. Print the sorted list and the median. Hint: sort with total_cmp, then the middle item of a list with an odd length is at index len() / 2.

Show solution

fn main() {
    let mut prices: Vec<f64> = vec![3.5, 1.25, 9.0, 4.75, 2.0];

    prices.sort_by(|a, b| a.total_cmp(b));
    let median = prices[prices.len() / 2];

    println!("sorted: {:?}", prices);
    println!("median: {median}");
}

Output:

sorted: [1.25, 2.0, 3.5, 4.75, 9.0]
median: 3.5

▶ Try it Yourself

The Vec<f64> type annotation matters. Without it, Rust doesn’t yet know which float type the numbers are when it reaches total_cmp, and it refuses to compile with “no method named total_cmp”.

Recap

• sort() and sort_unstable() sort in place, smallest first. Use reverse(), y.cmp(x), or Reverse for largest first.
• Floats can’t use sort() because of NaN. Use sort_by(|a, b| a.total_cmp(b)).
• sort_by_key sorts by a chosen field; sort_by with .then_with() sorts by several fields.
• dedup() only removes neighbours that are equal, so sort first.
• contains, position, max/min, and max_by_key search any list; binary_search is much faster but needs a sorted list.

Quick check

Quick check

1. Why does vec![1.5, 0.5].sort() fail to compile?

Floats can't be stored in a Vec sort only works on strings Floats don't implement Ord, because NaN can't be compared The vector isn't mut

2. What does vec![1, 1, 2, 1].dedup() leave in the vector?

[1, 2] [1, 2, 1] [2] [1, 1, 2, 1]

3. What does vec![10, 20, 30].binary_search(&25) return?

Err(2) Ok(2) None -1

4. In a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)), when is the name compared?

Always, before the grade Never Only when the names are different Only when the two grades are equal

Score: 0 / 4

Read more

• Slice methods: sort, sort_by, binary_search and more — standard library docs: every sorting and searching method, with notes on speed and stability.
• std::cmp::Ordering — standard library docs: Less, Equal, Greater, plus then, then_with and reverse.
• std::cmp::Reverse — standard library docs: the wrapper for sorting a key from largest to smallest.
• f64::total_cmp — standard library docs: exactly where NaN, negative zero and infinity end up when you sort floats.
• Sort a Vector — Rust Cookbook: short recipes for sorting integers, floats and structs.