Rust Reference ยท Collections
Rust sort, sort_by and sort_unstable
Reference for sorting slices in Rust: sort, sort_by, sort_by_key, sort_unstable, sort_by_cached_key, floats with total_cmp, stability and complexity.
Sorting is a slice method, so it works on arrays and on Vec<T> alike, and it sorts in place. sort() needs T: Ord. When the element type cannot be ordered by default, or you want a different order, sort_by takes a comparison closure and sort_by_key takes a key-extraction closure.
There are two families. sort* is stable (equal elements keep their original relative order). sort_unstable* may reorder equal elements, but it is usually a little faster and needs no extra memory.
let mut v = vec![3, 1, 2]; v.sort(); // [1, 2, 3] v.sort_by(|a, b| b.cmp(a)); // [3, 2, 1]
Try it
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.
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.
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.
Syntax
impl<T> [T] { pub fn sort(&mut self) where T: Ord; pub fn sort_by<F: FnMut(&T, &T) -> Ordering>(&mut self, compare: F); pub fn sort_by_key<K: Ord, F: FnMut(&T) -> K>(&mut self, f: F); pub fn sort_by_cached_key<K: Ord, F: FnMut(&T) -> K>(&mut self, f: F); pub fn sort_unstable(&mut self) where T: Ord; pub fn sort_unstable_by<F: FnMut(&T, &T) -> Ordering>(&mut self, compare: F); pub fn sort_unstable_by_key<K: Ord, F: FnMut(&T) -> K>(&mut self, f: F); pub fn is_sorted(&self) -> bool where T: PartialOrd; }
| Name | Description |
|---|---|
compare |
Returns Ordering::Less, Equal or Greater for two elements. It must be a consistent total order. |
f |
Derives a sort key from one element. The key type must be Ord. |
Returns: nothing; the slice is reordered in place.
Panics and edge cases: a comparison that is not a total order (for example partial_cmp(..).unwrap() with NaN present) can panic or leave the result unspecified. Since Rust 1.81 the sort may panic when it detects that the ordering is inconsistent, but it never causes undefined behavior.
Usage notes
- Complexity: all are O(n log n) in the worst case. The stable sort allocates up to half the slice length of scratch memory;
sort_unstablesorts in place. - Floats are not
Ord, sov.sort()on aVec<f64>does not compile. Usesort_by(|a, b| a.total_cmp(b)), which also gives NaN a defined position. - Descending order: reverse the comparison (
b.cmp(a)), sort byReverse(key), or sort then callreverse(). - Multi-level ordering: return a tuple key, or chain
Ordering::then/then_with. sort_by_keycalls the key function many times per element and the key cannot borrow from the element; usesort_by_cached_keyfor expensive or allocating keys such asto_lowercase().- Choose unstable when equal elements are indistinguishable (plain numbers) or when you will not care about their relative order.
- Check first:
is_sorted()tests without sorting. A sorted slice enablesbinary_search. - Sort a sub-range by slicing:
v[2..6].sort().