Sort

Sorting a vector of Strings in Rust can be done with a single function call. But more complex sorting, like with 2 properties at once, requires a custom function.

By returning Ordering, we can use a custom function with the sort_by and sort_unstable_by functions. In this way we can implement more complex, compound sorting routines.

To begin, we need to add a "use" statement at the top of the program for "cmp" to access Ordering. In main, we add 5 Strings to a vector.

use std::cmp::*;

fn compare_len_reverse_alpha(a: &String, b: &String) -> Ordering {
    // Sort by length from short to long first.
    let length_test = a.len().cmp(&b.len());
    if length_test == Ordering::Equal {
        // If same length, sort in reverse alphabetical order.
        return b.cmp(&a);
    }
    return length_test;
}

fn main() {
    // The vec we want to sort.
    let mut animals = vec![];
    animals.push("bird".to_string());
    animals.push("elephant".to_string());
    animals.push("cat".to_string());
    animals.push("ant".to_string());
    animals.push("bat".to_string());

    // Call the function that returns Ordering.
    animals.sort_unstable_by(compare_len_reverse_alpha);

    // Print results.
    println!("{:?}", animals);
}
["cat", "bat", "ant", "bird", "elephant"]

Sort by key

Sometimes we want to sort a vector by only part of each element (like a key). This can be done with the sort_by_key function.

fn main() {
    let mut items = vec![(10, 1), (0, 2), (30, 0)];
    // Sort by the second value in each tuple.
    items.sort_by_key(|x| x.1);
    println!("{:?}", items);
}
[(30, 0), (10, 1), (0, 2)]

Cached key

If we want to sort a collection in a more complex way, it can take some time to compute each key. With sort_by_cached_key, we avoid computing this information more than once.

fn count_letter(value: &str, letter: char) -> usize {
    value.chars().filter(|&x| x == letter).count()
}

fn main() {
    let mut words = vec!["window", "work", "cat"];
    // Sort by count of letter "w" from low to high.
    words.sort_by_cached_key(|x| count_letter(x, 'w'));
    println!("{:?}", words);
}
["cat", "work", "window"]

Cached keys benchmark

When can using sort_by_cached_key improve performance over just calling sort_by_key? Usually if some sort of allocation occurs, cached keys help.

use std::time::*;

fn uppercase_count_letter(value: &str, letter: char) -> usize {
    value
        .to_ascii_uppercase()
        .chars()
        .filter(|&x| x == letter)
        .count()
}

fn main() {
    let mut words = vec!["window", "work", "cat", "www"];
    if let Ok(max) = "10000000".parse::<usize>() {
        // Version 1: use cached keys.
        let t0 = Instant::now();
        for _ in 0..max {
            words.sort_by_cached_key(|x| uppercase_count_letter(x, 'W'));
        }
        println!("{} ms", t0.elapsed().as_millis());

        // Version 2: use keys.
        let t1 = Instant::now();
        for _ in 0..max {
            words.sort_by_key(|x| uppercase_count_letter(x, 'W'));
        }
        println!("{} ms", t1.elapsed().as_millis());
    }
}
1696 ms
2215 ms

Sort_unstable

This benchmark aims to determine how much performance we can gain from using sort_unstable. It uses a small array of only 8 elements.

use std::time::Instant;

fn main() {
    let items_original = [10, 20, 5, -10, 100, 200, -200, 0];
    if let Ok(max) = "100000000".parse::<usize>() {
        // Version 1: use sort.
        let t0 = Instant::now();
        for i in 0..max {
            let mut items = items_original;
            items.sort();
            if items[0] != -200 {
                break;
            }
        }
        println!("{:?}", t0.elapsed());

        // Version 2: use sort_unstable.
        let t1 = Instant::now();
        for i in 0..max {
            let mut items = items_original;
            items.sort_unstable();
            if items[0] != -200 {
                break;
            }
        }
        println!("{:?}", t1.elapsed());
    }
}
500.9585  ms    sort
476.249709ms    sort_unstable

We implemented a compound sort on a string vector in Rust. Often we need to sort by one aspect, and then by another—a custom Ordering function is needed for this.