Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 132 ยท Collections and Iterators

Sorting, Searching and Comparison

Learn to sort and search in Rust - sort, sort_by, sort_by_key, sort_unstable, Ordering, Reverse, sorting floats with total_cmp, binary_search, derive Ord and stable versus unstable sorts.

Sorting looks like a one-liner in most languages: list.sort(). Rust has that too, but it also asks a sharper question: what does "smaller" mean for this type? The answer lives in a few comparison traits, and once you understand them, sorting by several fields, sorting in reverse, sorting floats and searching a sorted list all follow the same small set of tools.

This lesson covers sort, sort_by, sort_by_key, the Ordering type, Reverse, floats and NaN, deriving Ord for your own structs, stable versus unstable sorts, and binary search. The methods live on slices, so they work on arrays, Vec and any &mut [T].

sort and the Ord trait

v.sort() sorts a slice in place in ascending order. It needs the element type to implement Ord, the trait for total orderings: any two values can be compared and the result is consistent. Integers, char, bool, String, &str, tuples and Vecs of Ord types are all Ord.

Rust Basic sorting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

String ordering is by bytes (Unicode code points), so uppercase letters sort before lowercase: "Apple" and "Banana" come before "apple". For human-friendly, case-insensitive or locale-aware ordering, you must supply your own key or comparison. sort returns (); it changes the slice rather than returning a sorted copy. To keep the original, clone first, or collect and sort.

Ordering and cmp

Every comparison boils down to the Ordering enum, with three variants: Less, Equal and Greater. The cmp method on any Ord type returns one, and Ordering has helpers such as reverse() and then()/then_with(), which chain comparisons.

Rust Ordering values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

sort_by and sort_by_key

When the natural order is not what you want, use one of two methods:

  • sort_by(|a, b| ...) takes a closure returning an Ordering; it can express anything.
  • sort_by_key(|item| key) takes a closure returning a key; the slice is ordered by comparing keys. It is shorter when one field decides.
Rust sort_by and sort_by_key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

std::cmp::Reverse is a wrapper that flips the order of whatever it holds, which makes it perfect for "descending" inside a key or a tuple. Swapping the arguments (b.score.cmp(&a.score)) does the same in a sort_by closure.

Notice the first sort printed Bob (19) before Amy and Cat (both 24), and in the second sort, Zed and Bob (both 90) stayed in the order from the previous sort. That is stability, described below.

sort_by_key calls the key closure every time it compares, which can mean many calls per element. If the key is expensive (like to_lowercase, which allocates), use sort_by_cached_key: it computes each key once and stores it, at the cost of extra memory.

Sorting floats

f32 and f64 are not Ord, because NaN is not equal to, less than or greater than anything, including itself. So floats.sort() is a compile error, and so is floats.iter().max().

Rust Sorting f64 does not compile (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The error is error[E0277]: the trait bound `f64: Ord` is not satisfied. There are two fixes. If you know there is no NaN, use partial_cmp(...).unwrap(). If there might be, use total_cmp, which defines a total order over all floats (negative NaN first, then negatives, zeros, positives, positive NaN last).

Rust Sorting floats with total_cmp

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Deriving ordering for your own types

For structs and enums, #[derive(PartialEq, Eq, PartialOrd, Ord)] generates a lexicographic comparison: fields are compared in the order they are declared, and enum variants in declaration order. That is handy, but only if the field order matches what you want.

Rust derive Ord on structs and enums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

If you need a different order, write impl Ord by hand (with a matching PartialOrd that calls Some(self.cmp(other))) or just sort with sort_by_key. Keep Ord consistent with Eq: if cmp says Equal, then == must be true. A BinaryHeap and BTreeMap depend on that.

Stable and unstable sorts

A sort is stable if elements that compare equal keep their original relative order. sort, sort_by and sort_by_key are stable. The sort_unstable* family makes no promise, but it is usually faster, needs no extra memory, and is often what you want for plain numbers where "equal" means "identical" and stability is invisible.

Rust Stable versus unstable

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rule of thumb: use sort/sort_by_key when you sort records by one field and care about the previous order (sort by name, then stable-sort by department); use sort_unstable when equal elements are indistinguishable.

Searching

For an unsorted list, search linearly with contains, iter().position, iter().find or starts_with on slices. For a sorted slice, binary_search finds an element in O(log n) comparisons instead of O(n). It returns a Result<usize, usize>: Ok(index) if found, or Err(index) with the position where the value could be inserted to keep the slice sorted.

Rust binary_search and friends

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Binary search silently gives wrong answers if the slice is not sorted by the same ordering you search with. It does not panic or warn. Also, with duplicates it may return any matching index; partition_point gives you the first or last boundary reliably.

Other useful comparison tools

  • iter().max_by_key(|x| ...) and min_by_key find extremes without sorting.
  • select_nth_unstable(k) moves the k-th smallest element into place in O(n), good for medians.
  • v.dedup() removes consecutive duplicates, so sort first.
  • a.cmp(&b) on slices and strings compares lexicographically; a.eq_ignore_ascii_case(b) compares ASCII text without allocating.
  • BTreeMap/BTreeSet keep their keys sorted all the time, which is better than re-sorting a Vec after every insert.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does vec_of_f64.sort() not compile?

    sort requires Ord. f64 is only PartialOrd. Use sort_by(|a, b| a.total_cmp(b)), or partial_cmp(..).unwrap() when NaN cannot occur.
  2. 2. How do you sort a Vec<Player> by score from highest to lowest?

    std::cmp::Reverse flips the comparison of the key, giving descending order. sort() returns (), so it cannot be chained.
  3. 3. What does [1, 3, 5].binary_search(&4) return?

    4 is not present. Err(i) holds the index where it could be inserted to keep the slice sorted: between 3 and 5, which is index 2.
  4. 4. Which statement about sort_by_key and sort_unstable_by_key is correct?

    Stable sorts keep equal elements in their original relative order. Unstable sorts do not promise that, which lets them be faster and use no extra memory.
  5. 5. What does #[derive(PartialOrd, Ord)] on a struct compare?

    Derived ordering is lexicographic over fields in declaration order (and enum variants in declaration order). Reorder the fields, or write impl Ord, if you need a different priority.

Summary

  • sort() needs Ord; sort_by takes a closure returning Ordering; sort_by_key takes a key (tuples give multi-field sorts, Reverse gives descending).
  • Ordering is Less, Equal or Greater; chain comparisons with then and then_with.
  • Floats are only PartialOrd: sort with total_cmp (or partial_cmp().unwrap() when NaN is impossible).
  • derive(PartialOrd, Ord) compares fields in declaration order and enum variants in declaration order.
  • sort, sort_by, sort_by_key are stable; sort_unstable* are usually faster and need no extra memory.
  • sort_by_cached_key avoids recomputing expensive keys.
  • binary_search works only on slices sorted by the same ordering and returns Ok(index) or Err(insert_position); partition_point finds boundaries.

Next: Panics