Sorting

Recipe	Crates	Categories
Sort a Vector of Integers
Sort a Vector of Floats
Sort a Vector of Structs

No single crate is the "sorting crate", as the standard library is often sufficient.

The primary sorting methods are found on slices (&[T]). You'll typically call them on a Vec<T> or an array.

• slice::sort() is a stable sort, meaning if two elements are equal, their original relative order is preserved. It's an adaptive merge sort that performs well on many data patterns.
• slice::sort_unstable() is generally faster than the stable sort but doesn't guarantee the order of equal elements.
• slice::sort_by_key() sorts a slice based on a key extracted from each element.
• slice::sort_by() allows you to provide a custom comparison function for more complex sorting logic.

Start with sort_unstable() for the best performance. If you need to preserve the order of equal elements, use sort().

Note the following crates and modules:

• itertools provides an itertools::sorted function and a sorted() method on its Itertools trait. It sorts an iterator into a new Vec without needing to collect it first: (0..10).rev().sorted().collect::<Vec<_>>();
• std::cmp↗ provides ordering traits.

Sort a Vector of Integers

This example sorts a vector of integers via sort↗. Alternatively, use sort_unstable↗, which can be faster but does not preserve the order of equal elements.

/// This example demonstrates the basic usage of the `sort` method on a vector.
///
/// The `sort` method sorts the elements of the vector in ascending order.
fn main() {
    let mut vec = vec![1, 5, 10, 2, 15];

    // Sort the vector in ascending order.
    vec.sort();

    assert_eq!(vec, vec![1, 2, 5, 10, 15]);
    println!("{vec:?}");
}

Sort a Vector of Floats

sort and sort_unstable require the elements to implement the std::cmp::Ord↗ trait, which provides a total ordering.

Floats do not implement Ord trait (because they can be NaN, "not a number"), but they implement the std::cmp::PartialOrd↗ trait, which provides partial ordering.

A vector of f32↗ or f64↗ guaranteed not to contain NaN values can therefore be sorted using sort_by↗ and std::cmp::PartialOrd::partial_cmp↗.

/// Sort a vector of floats.
fn main() {
    let mut vec = vec![1.1, 1.15, 5.5, 1.123, 2.0];

    // ERROR: vec.sort();

    // The vector does not contain `f64::NAN`,
    // so we can sort it using `partial_cmp` safely:
    vec.sort_by(|a, b| a.partial_cmp(b).unwrap());

    assert_eq!(vec, vec![1.1, 1.123, 1.15, 2.0, 5.5]);

    println!("{vec:?}");
}

Sort a Vector of Structs

The following example sorts a vector of Person structs with properties name and age by its natural order (by name and age). In order to make the Person struct sortable, we need to implement four traits std::cmp::Eq↗, std::cmp::PartialEq↗, std::cmp::Ord↗ and std::cmp::PartialOrd↗. These traits can be simply derived with an attribute, producing a lexicographic ordering based on the top-to-bottom declaration order of the struct's members.

To sort in a different way, provide a custom comparator function to the std::vec::Vec::sort_by↗ method:

/// A struct with `name` and `age` fields.
#[derive(Debug, Eq, Ord, PartialEq, PartialOrd)]
struct Person {
    name: String,
    age: u32,
}

impl Person {
    /// Constructor for creating a new `Person` instance.
    pub fn new(name: String, age: u32) -> Self {
        Person { name, age }
    }
}

fn main() {
    let mut people = vec![
        Person::new("Zoe".to_string(), 25),
        Person::new("Al".to_string(), 60),
        Person::new("John".to_string(), 1),
    ];

    // Sort people by derived natural order (in this case, name and age):
    people.sort();

    assert_eq!(
        people,
        vec![
            Person::new("Al".to_string(), 60),
            Person::new("John".to_string(), 1),
            Person::new("Zoe".to_string(), 25),
        ]
    );
    println!("{people:?}");

    // Sort people by age only:
    people.sort_by(|a, b| b.age.cmp(&a.age));

    assert_eq!(
        people,
        vec![
            Person::new("Al".to_string(), 60),
            Person::new("Zoe".to_string(), 25),
            Person::new("John".to_string(), 1),
        ]
    );

    // You can also use `sort_by_key`:
    people.sort_by_key(|p| p.age);

    println!("{people:?}");
}

See Also

• glidesort↗ is a Rust implementation of Glidesort, a stable adaptive quicksort/mergesort hybrid sorting algorithm.

Related Topics

• Data Structures.
• B-trees.