Sorting in Rust

In order to sort a Vec we can use the .sort() method, which sorts the elements of a given Vec in ascending order (default), descending order or user-defined order.

Syntax:

The syntax of the sorting methods is:

vec.sort();                           // ascending order (default)
vec.sort_by(|a, b| a.cmp(b));        // with custom comparator
vec.sort_by_key(|k| /* key expr */); // sort by a key

Let's see some examples below. Sorting a Vec of integers in ascending order

let mut numbers = vec![11, 3, 7, 5, 2];

numbers.sort(); // numbers becomes [2, 3, 5, 7, 11]

Sorting a Vec of integers in descending order

let mut numbers = vec![11, 3, 7, 5, 2];

numbers.sort_by(|a, b| b.cmp(a));

Sorting a Vec of Strings in descending order

let mut names = vec!["Mircea", "Andy", "Xavier", "Michael", "Christina"];

names.sort_by(|a, b| b.cmp(a));  // --> ["Xavier", "Mircea", "Michael", "Christina", "Andy"]

Sort with custom function (comparator):

sort_by() supports a basic comparison function that we can use to specify how we want to sort:

fn compare(a: &i32, b: &i32) -> std::cmp::Ordering {
    a.cmp(b)
}

This can be written as a lambda function (nameless function we can easily pass to sort_by()) as follows:

|a: &i32, b: &i32| -> std::cmp::Ordering {
    a.cmp(b)
}

We can make it even shorter by dropping the type annotations since sort_by() will infer the types. We use .cmp() which directly returns std::cmp::Ordering

|a, b| a.cmp(b)

When the sort_by() function compares two values, it sends the values to the compare function, and sorts the values according to the returned value:

• If the result is Ordering::Less then a is sorted before b.
• If the result is Ordering::Greater then b is sorted before a.

All we need to is using the compare function (as a lambda function) inside the sort_by() function:

let mut numbers = vec![3, 23, 12];

// using the short version of the lambda function
numbers.sort_by(|a, b| a.cmp(b)); // --> 3, 12, 23

To demonstrate a basic example, let's assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the len() method of each string to compare them.

let mut words = vec!["banana", "pie", "Washington", "book"];

words.sort_by_key(|a| a.len()); // --> ["pie", "book", "banana", "Washington"]

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array consisting of two numbers.

let mut pairs = vec![vec![1, 5], vec![12, 5], vec![10, 1], vec![1, 3]];

pairs.sort_by(|a, b| {
    // in case the first values of each pair are equal,
    // compare them using their second values
    if a[0] == b[0] {
        a[1].cmp(&b[1])
    } else {
        a[0].cmp(&b[0])
    }
});
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]

Time Complexity:

Sorting a Vec via .sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the Vec.

It takes O(1) (constant time) to compare two numbers, therefore sorting a Vec of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting a Vec of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort() method sorts the elements of a Vec in place (it changes the Vec directly and returns nothing), but it is a stable sort that may allocate a temporary buffer of up to the size of the Vec, so the extra space used is O(n). sort_unstable() needs no such buffer.

Assignment
Follow the Coding Tutorial and let's sort some Vecs.

Hint
Look at the examples above if you get stuck.