Sorting in Rust 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 (transforms the Vec directly, using no auxiliary data structure), so the extra space used for this is O(1).

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

Hint
Look at the examples above if you get stuck.