Sorting and searching

Sorting a slice is one method call, and the ordering it uses is the one the element type implements. sort needs Ord, sort_by takes a comparison closure and sort_by_key takes a key function. All three reorder the slice in place and are stable.

The methods work on a slice, so a Vec needs to be mutable and an array needs to be a mutable binding as well. Searching a sorted slice is binary_search, which returns Ok(index) or the Err insertion point. The two methods belong together: a binary search on an unsorted slice silently returns a wrong answer, which the lesson warns about before the error section.

sort and sort_by

values.sort() orders a mutable slice by the natural order of its elements. sort_by takes a closure that compares two items and returns an Ordering, which is how a custom rule is written.

The program sorts five integers, then sorts three words by length. The numbers come out ascending and the words shortest first.

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

rustc --edition 2024 sort.rs
./sort

[1, 1, 3, 4, 5]

A comparison closure may do anything, including reading a second field, which is why `sort_by` is the general form and `sort_by_key` the convenient one. The sort is stable: two items that compare equal keep the order they had, and the program relies on that in the next section. The length ordering is written with a.len().cmp(&b.len()), which the lesson on closures passes as an argument. A descending order swaps the two sides of the comparison.

sort_by_key

When the rule is a value derived from each item, sort_by_key is shorter. It calls the function once per comparison, so a cheap key such as a length or a field is the right choice.

The program sorts three people by age and prints them. Two of them share an age, and the stable sort keeps their original order.

fn main() { let mut words = vec!["banana", "fig", "cherry"]; words.sort_by(|a, b| a.len().cmp(&b.len())); println!("{words:?}"); }

rustc --edition 2024 sort_by.rs
./sort_by

["fig", "banana", "cherry"]

The people are printed in the sorted order with their ages. The lesson on text files sorts lines the same way before printing them, so a report is deterministic.

binary_search

binary_search needs a sorted slice and returns Ok with the index of the value or Err with the position where it would be inserted. is_sorted checks the precondition in one pass.

The program searches for five and for four in a sorted array. The first is found at index two, the second would go at index two, and the array is reported as sorted.

fn main() { let values = [1, 3, 5, 7, 9]; println!("{:?}", values.binary_search(&5)); println!("{:?}", values.binary_search(&4)); println!("{}", values.is_sorted()); }

rustc --edition 2024 binary_search.rs
./binary_search

Ok(2)
Err(2)
true

The Err variant carries the insertion point, which is what makes the next section possible without a second search.

A sorted insert

An insert that keeps the order is a binary search followed by a Vec::insert at the returned index. The search is logarithmic and the insert is linear, because the elements after the position move.

The program inserts four into a sorted vector and prints the result. The geometry of the method is the same one the standard library uses for a sorted collection.

fn main() { let mut values = vec![1, 3, 5]; match values.binary_search(&4) { Ok(index) => println!("found {index}"), Err(index) => values.insert(index, 4), } println!("{values:?}"); }

rustc --edition 2024 sorted_insert.rs
./sorted_insert

[1, 3, 4, 5]

The `Vec::insert` shifts every element after the position, so a hundred inserts into a large vector cost more than the searches that found the positions. A collection that inserts and searches like this for a living is the set from the lesson on sets, which keeps the order in a tree.

A type without Ord

sort requires Ord on the element type. A struct without the derive has no ordering, and the compiler reports E0277 with a suggestion to derive it.

The program sorts two people with only a name field and no derive. The error names the trait and the method, and the help adds the attribute.

struct Person { name: &'static str, } fn main() { let mut people = vec![Person { name: "ada" }, Person { name: "alan" }]; people.sort(); println!("{}", people.len()); }

rustc --edition 2024 not_ord_err.rs

error[E0277]: the trait bound `Person: Ord` is not satisfied
--> not_ord_err.rs:7:12
|
7 | people.sort();
| ^^^^ the trait `Ord` is not implemented for `Person`
|
note: required by a bound in `slice::<impl [T]>::sort`
--> /rustc/31fca3adb283cc9dfd56b49cdee9a96eb9c96ffd/library/alloc/src/slice.rs:131:4
help: consider annotating `Person` with `#[derive(Ord)]`
|
1 + #[derive(Ord)]
2 | struct Person {
|

error: aborting due to 1 previous error

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

Deriving Ord compares the fields in declaration order, which may not be the rule the program wants. In that case sort_by_key states the rule explicitly.

Exercises

1. Sort a vector of words by length and then alphabetically within the same length.
2. Search a sorted vector of strings for a missing word and print the insertion point.
3. Add a second field to the person struct and sort by it with a key function.

The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev