How to sort a Vec

Short answer: vec.sort() sorts in place and needs the elements to implement Ord. When the natural order isn’t the order you want, vec.sort_by(|a, b| …) takes a comparator of your own. vec.sort_unstable() does the same job without the stability promise — usually a little faster, and it never allocates.

sort() is the default

In a fresh project (cargo new sort-demo), replace src/main.rs with this and run cargo run:

fn main() {
    let mut numbers = vec![3, 1, 4, 1, 5, 9, 2, 6];
    numbers.sort();
    println!("{numbers:?}");

    let mut names = vec!["Grace", "Ada", "Edsger", "Barbara"];
    names.sort();
    println!("{names:?}");
}

▶Run this in the Rust Playground

[1, 1, 2, 3, 4, 5, 6, 9]
["Ada", "Barbara", "Edsger", "Grace"]

Numbers sort ascending and so do strings, lexicographically. sort needs T: Ord, which every integer type, char, bool, String, &str and tuples of Ord types implement. The sort happens in place: the Vec’s own buffer is rearranged.

Sorting needs mut

sort takes &mut self, so the binding has to be mutable. Leave the mut off and the compiler stops the build before anything runs:

fn main() {
    let numbers = vec![3, 1, 2];
    numbers.sort();
    println!("{numbers:?}");
}

▶Run this in the Rust Playground

error[E0596]: cannot borrow `numbers` as mutable, as it is not declared as mutable
 --> src/main.rs:3:5
  |
3 |     numbers.sort();
  |     ^^^^^^^ cannot borrow as mutable
  |
help: consider changing this to be mutable
  |
2 |     let mut numbers = vec![3, 1, 2];
  |         +++

For more information about this error, try `rustc --explain E0596`.

The rule is about the binding, not the call site — why Rust requires the mut keyword has the details.

sort_by: your own comparator

sort_by takes a closure that is handed two elements as references and returns an Ordering: Less, Equal or Greater. Two comparators worth knowing, one that folds case and one that reverses:

fn main() {
    let mut names = vec!["Barbara", "ada", "Edsger"];
    names.sort_by(|a, b| a.to_lowercase().cmp(&b.to_lowercase()));
    println!("{names:?}");

    let mut scores = vec![10, 25, 5, 30];
    scores.sort_by(|a, b| b.cmp(a));
    println!("{scores:?}");
}

▶Run this in the Rust Playground

["ada", "Barbara", "Edsger"]
[30, 25, 10, 5]

a.to_lowercase().cmp(&b.to_lowercase()) compares the folded strings, so case stops mattering for the order. It allocates two Strings per comparison — fine for a short list, wasteful for a long one. Flipping the operands, b.cmp(a), is the whole trick behind reverse order. sort_by_key is the shortcut when the sort key is one field of the element; sorting structs by a field is the next article’s subject.

Floats have no Ord

f64 implements PartialOrd, not Ord, because NaN compares unequal to itself and no total order survives that. So sort refuses the whole Vec:

fn main() {
    let mut scores: Vec<f64> = vec![2.5, 0.5, 1.5];
    scores.sort();
    println!("{scores:?}");
}

▶Run this in the Rust Playground

error[E0277]: the trait bound `f64: Ord` is not satisfied
   --> src/main.rs:3:12
    |
  3 |     scores.sort();
    |            ^^^^ the trait `Ord` is not implemented for `f64`
    |
    = help: the following other types implement trait `Ord`:
              i128
              i16
              i32
              i64
              i8
              isize
              u128
              u16
            and 4 others
note: required by a bound in `slice::<impl [T]>::sort`
   --> /Users/rango/.rustup/toolchains/1.99.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/alloc/src/slice.rs:133:12
    |
131 |     pub fn sort(&mut self)
    |            ---- required by a bound in this associated function
132 |     where
133 |         T: Ord,
    |            ^^^ required by this bound in `slice::<impl [T]>::sort`

For more information about this error, try `rustc --explain E0277`.

sort_by with partial_cmp sorts floats that are known to contain no NaN:

fn main() {
    let mut scores: Vec<f64> = vec![2.5, 0.5, 1.5];
    scores.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{scores:?}");

    let mut with_nan: Vec<f64> = vec![2.0, f64::NAN, 1.0];
    with_nan.sort_by(|a, b| a.total_cmp(b));
    println!("{with_nan:?}");
}

▶Run this in the Rust Playground

[0.5, 1.5, 2.5]
[1.0, 2.0, NaN]

partial_cmp returns an Option because the comparison can fail, and .unwrap() panics on NaN. When NaNs are possible, f64::total_cmp defines a total order: positive NaN sorts after every number, negative NaN before them.

sort_unstable: no promise about equal elements

A stable sort keeps elements that compare equal in their original relative order. For numbers the promise is invisible, because equal numbers are indistinguishable. It shows up when equal elements carry different data:

fn main() {
    let pairs: Vec<(i32, usize)> = (0..40).map(|i| ((i % 4) as i32, i)).collect();

    let mut stable = pairs.clone();
    stable.sort_by(|a, b| a.0.cmp(&b.0));

    let mut unstable = pairs.clone();
    unstable.sort_unstable_by(|a, b| a.0.cmp(&b.0));

    println!("stable:   {:?}", zeros(&stable));
    println!("unstable: {:?}", zeros(&unstable));
}

fn zeros(v: &[(i32, usize)]) -> Vec<usize> {
    v.iter().filter(|p| p.0 == 0).map(|p| p.1).collect()
}

▶Run this in the Rust Playground

stable:   [0, 4, 8, 12, 16, 20, 24, 28, 32, 36]
unstable: [0, 36, 4, 8, 12, 16, 20, 24, 28, 32]

Each of the four keys appears ten times. Both sorts put the key-0 elements in the same place in the list; only their order inside that group differs, and only the stable sort keeps it ascending. On short lists the two algorithms often produce the same order anyway, which is why a small example can’t show the difference. The two clones give each sort the original order to work from; when you should clone covers what they cost.

The standard library documents sort as stable and sort_unstable as in-place, never allocating. Measured with a counting global allocator under 1.99.0, sorting a 1,000-element Vec costs sort one allocation and sort_unstable zero; at 256 elements neither allocates. sort_unstable_by is the comparator version. sort, sort_by and sort_unstable are slice methods, so arrays and &mut [T] windows sort the same way.

Related

• Why does Rust require the mut keyword? — the binding-level mut sort needs
• What is the difference between a Vec and a slice? — why a window into a Vec sorts in place
• When should you clone? — the two clones in the last example

Next in this chapter: how to sort a Vec of structs by a field.