🎓 A1Learner
🔍

Rust Sorting

Sorting is the set of list tools that put values into order and search the result. Companion tools flip the order or sort by a key.

Smallest first

sort() orders numbers and text with no arguments at all.

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

Largest first

sort_by takes a comparison: b.cmp(a) asks the question backwards and flips the order.

scores.sort_by(|a, b| b.cmp(a));
println!("{:?}", scores);

The same flip, less typing (Reverse)

Wrap the key in Reverse and sort_by_key does the flipping for you.

use std::cmp::Reverse;

let mut scores = vec![42, 7, 19, 7];
scores.sort_by_key(|&s| Reverse(s));
println!("{:?}", scores);

Sort by one field

Sort people by age with sort_by_key: the key decides the order, the items tag along.

let mut people = vec![("Zoe", 25), ("Al", 60), ("John", 1)];
people.sort_by_key(|person| person.1);
println!("{:?}", people);

Decimals need a total order

f64 cannot promise a full order (NaN ruins it), so plain sort() refuses. Pass f64::total_cmp to sort_by: it orders every pair and puts NaN last.

let mut temps = vec![21.5, 18.0, 23.25, 19.75];
temps.sort_by(f64::total_cmp);
println!("{:?}", temps);

Search a sorted list

On the sorted list from the first example, binary_search finds a value in a few jumps instead of a scan.

println!("{:?}", scores.binary_search(&19));

Example

use std::cmp::Reverse;

fn main() {
    let mut board = vec![
        ("Zoe", 40),
        ("Al", 75),
        ("John", 75),
        ("Kim", 20),
    ];
    board.sort_by_key(|&(name, score)| (Reverse(score), name));
    println!("Scoreboard:");
    for (name, score) in &board {
        println!("{name}: {score}");
    }
    println!("players = {}", board.len());
}

Key points

  • sort() is stable: equal items keep their original order.
  • sort_unstable() may swap them but can be faster — pick sort() unless you measured.
  • sort() needs the item type to have a total order (Ord).
  • Numbers and text qualify.
  • For decimals, see the total_cmp snippet.
  • binary_search returns Ok(index) when the value is there.
  • It returns Err(index) where the value would fit.
  • For 8 in [7, 7, 19, 42], that is Err(2).
  • Sort first, then search.
  • Sorting tools order a list and help search the ordered result.

sort_by_key with (Reverse(score), name) sorts by score largest-first. It breaks ties by name. Tuples compare left to right. So the second key only matters when the first is equal. Al and John tie at 75, so the names decide their order. The key function runs during the sort, so keep it cheap: a field read and a Reverse.

Note

Never binary_search an unsorted list: it answers with confidence and is wrong.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

What does binary_search return for a value that is missing?