Sorting in Rust

You are dealt a hand of cards, and you want them in order. You pick up one card at a time and slide it into the right gap among the cards you already hold. Nobody taught you that. You just do it.

That is sorting. Sorting means rearranging items so they sit in order, smallest to largest, or A to Z, or newest first. It is the most common job in a program. Leaderboards, search results, and your phone's contact list all depend on it.

Sorting also unlocks other tricks. Once a list is sorted, you can find things in it very quickly (lesson 14), and duplicates end up side by side. Many problems that look hard become easy after one sort.

Reach for the standard library's sort almost every time. You still learn how sorting works, because it teaches you how to think about cost, and because interviewers love to ask.

Here are three classic ideas. Each one is a different answer to "how do I put a pile in order?".

Insertion sort is your hand of cards. Keep the left part sorted. Take the next item and slide it left until it sits in order. In the picture, the 1 slides all the way to the front, and the 3 slots in the middle. It is simple and quick on a list that is nearly sorted already. But a card might need to slide a long way, so on a reversed list of n items it does about n × n steps.

Merge sort works by splitting. Cut the pile in half, sort each half, then merge the two sorted halves. Merging is easy, because you only ever look at the front card of each pile and take the smaller. Try it on 1, 4, 6 and 2, 3, 7. Front cards 1 and 2: take 1. Front cards 4 and 2: take 2. Then 3, then 4, then 6, then 7. You get 1, 2, 3, 4, 6, 7 after a single walk through both piles.

But how do the halves get sorted? The same way: split again, until each pile has one card. A pile of one card is already sorted. Doing a thing by asking a smaller copy of itself is called recursion, and lesson 16 is all about it.

How many times can you cut n cards in half? About log n times (so 1,000 cards halve about 10 times). Each level of cutting costs one walk of n steps to merge. That gives n × log n in total, written O(n log n).

Quicksort picks one item, the pivot, and sorts around it. Everything smaller goes to its left, everything bigger goes to its right. Now the pivot is exactly where it belongs, forever. Then do the same to the left pile and the right pile. If the pivot lands near the middle each time, you get the same O(n log n) as merge sort. If you are unlucky, and keep picking the smallest item, it slows to O(n²). Real libraries pick pivots carefully to avoid that.

Remember: insertion sort slides, merge sort splits and zips, quicksort picks a pivot. The fast two both work by splitting the pile.

Start with insertion sort. It sorts in place, which means it rearranges the slice you give it and makes no copy.

/// Sorts a slice by growing a sorted hand from the left, like cards.
pub fn insertion_sort(cards: &mut [i32]) {
    for i in 1..cards.len() {
        // Walk the new card left until it sits in order.
        let mut j = i;
        while j > 0 && cards[j - 1] > cards[j] {
            cards.swap(j - 1, j);
            j -= 1;
        }
    }
}

cards[..i] is always the sorted hand. For each new card at i, the loop swaps it with its left neighbour while that neighbour is bigger. When the neighbour is no bigger, or the card reaches the front, it stops. for i in 1..cards.len() starts at 1 because a hand of one card is already sorted. The Playground link runs the demo that follows.

Now merge sort. It builds a new Vec and leaves the input alone.

/// Splits in half, sorts each half, then zips the two sorted halves together.
pub fn merge_sort(items: &[i32]) -> Vec<i32> {
    // Zero or one item is already sorted. This is what stops the splitting.
    if items.len() <= 1 {
        return items.to_vec();
    }
    let (left, right) = items.split_at(items.len() / 2);
    merge(&merge_sort(left), &merge_sort(right))
}

/// Combines two sorted lists into one sorted list.
pub fn merge(a: &[i32], b: &[i32]) -> Vec<i32> {
    let mut out = Vec::with_capacity(a.len() + b.len());
    let (mut i, mut j) = (0, 0);
    while i < a.len() && j < b.len() {
        // `<=` takes from the left on a tie, which keeps equal items in order.
        if a[i] <= b[j] {
            out.push(a[i]);
            i += 1;
        } else {
            out.push(b[j]);
            j += 1;
        }
    }
    // One side ran out. The other side is already sorted, so copy what is left.
    out.extend_from_slice(&a[i..]);
    out.extend_from_slice(&b[j..]);
    out
}

merge_sort is the splitting. split_at cuts the slice into a left and right half without copying anything. The line if items.len() <= 1 is the base case, the case simple enough to answer straight away. Without it the function would split forever. merge is the zipping. It keeps two positions, i and j, one for each pile, and takes the smaller front item each time. Once one pile runs out, the other is already in order, so extend_from_slice copies the rest in one go.

The <= in merge matters. When two items are equal, it takes the one from the left pile first. That keeps equal items in their original order, and the next section shows why that is a feature.

Remember: every recursive function needs a base case, a simple answer that stops it.

Finally, quicksort. Like insertion sort, it sorts in place.

/// Picks a pivot, puts smaller items before it and bigger after, then sorts
/// each side the same way.
pub fn quicksort(items: &mut [i32]) {
    if items.len() <= 1 {
        return;
    }
    let pivot_at = partition(items);
    let (left, right) = items.split_at_mut(pivot_at);
    quicksort(left);
    quicksort(&mut right[1..]); // index 0 of `right` is the pivot, already home
}

/// Moves the last item (the pivot) to its final place and returns that place.
/// Everything before it is smaller, everything after it is not.
fn partition(items: &mut [i32]) -> usize {
    let last = items.len() - 1;
    let pivot = items[last];
    let mut home = 0;
    for i in 0..last {
        if items[i] < pivot {
            items.swap(i, home);
            home += 1;
        }
    }
    items.swap(home, last);
    home
}

partition is the heart of it. It takes the last item as the pivot. It walks the slice, and every item smaller than the pivot is swapped into the next free slot at the front, tracked by home. At the end, the pivot swaps into home. Everything left of home is smaller, and home is the pivot's final place.

In real code you do not write your own sort. A slice already has them. The Playground link on this one runs it.

let mut scores = vec![72, 95, 41, 88, 60];
scores.sort(); // smallest first
assert_eq!(scores, [41, 60, 72, 88, 95]);

scores.sort_by(|a, b| b.cmp(a)); // largest first
assert_eq!(scores, [95, 88, 72, 60, 41]);

// Sort strings by length. Equal lengths keep their old order, because
// `sort` and `sort_by_key` are stable.
let mut words = vec!["pear", "fig", "apple", "kiwi", "plum"];
words.sort_by_key(|w| w.len());
println!("{:?}", words);
assert_eq!(words, ["fig", "pear", "kiwi", "plum", "apple"]);

// `f64` has no total order (NaN breaks it), so say how to compare.
let mut heights = vec![1.8, 1.5, 1.7];
heights.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(heights, [1.5, 1.7, 1.8]);

// `sort_unstable` can be a little faster, but equal items may swap places.
let mut ids = vec![5, 2, 9, 2];
ids.sort_unstable();
assert_eq!(ids, [2, 2, 5, 9]);

Here is what each one is for.

• sort() puts items in their natural order. It works for anything that has one, like numbers and strings.
• sort_by(|a, b| ...) lets you say how two items compare. Your closure returns an Ordering: less, equal or greater. b.cmp(a) flips the order.
• sort_by_key(|item| ...) sorts by a value you pull out of each item. It is the one you will use most. Sorting words by their length is one line.
• sort_unstable() is the same idea, but a little faster and it needs no extra memory.

Why does f64 need partial_cmp? Decimals have a value called NaN (short for "not a number"), and NaN is not smaller, bigger or equal to anything. So decimals have no full order, and Rust makes you handle that yourself rather than guess.

Stable or unstable? A sort is stable when items that compare equal keep the order they had before. sort, sort_by and sort_by_key are stable. sort_unstable makes no such promise. Here is when it shows up.

let mut results = vec![("Asha", 90), ("Ben", 75), ("Chen", 90), ("Dia", 75)];
results.sort_by_key(|&(_, marks)| marks);

// Ben came before Dia and Asha before Chen, and still do.
println!("{:?}", results);
assert_eq!(results, [("Ben", 75), ("Dia", 75), ("Asha", 90), ("Chen", 90)]);

Ben and Dia both got 75, and Ben was first in the list. A stable sort keeps Ben before Dia. Imagine a sports table sorted by points: if you sort by name first and then by points, a stable sort leaves teams on equal points in alphabetical order. An unstable sort would scramble them. If you do not care about the order of ties, sort_unstable is a fine choice.

To sort the biggest first, wrap the key in Reverse, the same type from lesson 8.

use std::cmp::Reverse;

let mut results = vec![("Asha", 90), ("Ben", 75), ("Chen", 92)];
// `Reverse` flips a key, so the biggest marks come first.
results.sort_by_key(|&(_, marks)| Reverse(marks));

println!("{:?}", results);
assert_eq!(results, [("Chen", 92), ("Asha", 90), ("Ben", 75)]);

Remember: use sort_by_key for most jobs, Reverse to flip it, and sort when ties must keep their order.

Insertion sort's best case is a list that is already sorted: each card needs no sliding, so it takes one pass. The standard library sorts are clever enough to spot runs that are already in order too. No comparison sort can beat O(n log n) in the worst case, which is why the fast ones all land there.

Each starter has a todo!(), a placeholder that panics if it runs. Replace it with your code.

pub fn sort_colors(colors: &mut [u8]) {
    todo!("0, 1 and 2 only: can one pass do it?")
}

pub fn sort_colors(colors: &mut [u8]) {
    // Three zones: 0s before `low`, 1s from `low` to `i`, 2s from `high` on.
    let (mut low, mut i, mut high) = (0, 0, colors.len());
    while i < high {
        match colors[i] {
            0 => {
                colors.swap(i, low);
                low += 1;
                i += 1;
            }
            1 => i += 1,
            _ => {
                high -= 1;
                // The item swapped in from the right is unchecked, so `i` stays.
                colors.swap(i, high);
            }
        }
    }
}

pub fn sort_words(words: &mut Vec<String>) {
    todo!("shortest first, and alphabetical among equal lengths")
}

pub fn sort_words(words: &mut Vec<String>) {
    // A tuple key compares its first part, then the second on a tie.
    words.sort_by(|a, b| (a.len(), a).cmp(&(b.len(), b)));
}

pub fn merge_intervals(intervals: &[(i32, i32)]) -> Vec<(i32, i32)> {
    todo!("sort by start, then fold overlapping ones together")
}

pub fn merge_intervals(intervals: &[(i32, i32)]) -> Vec<(i32, i32)> {
    let mut sorted = intervals.to_vec();
    sorted.sort(); // tuples sort by start first

    let mut merged: Vec<(i32, i32)> = Vec::new();
    for (start, end) in sorted {
        match merged.last_mut() {
            // It begins before the last one ends, so stretch the last one.
            Some(last) if start <= last.1 => last.1 = last.1.max(end),
            _ => merged.push((start, end)),
        }
    }
    merged
}

Sorting questions come in two kinds: "implement a sort" and "sort first, then solve". The second is far more common.

• Spot the signals. "Closest", "overlapping", "top k", "group together", and "in order" often mean sort first. If you catch yourself comparing every pair, ask whether a sort would put the answers side by side.
• Know the three costs by heart. Insertion is O(n²) and good on nearly sorted data. Merge is O(n log n) always, and needs extra space. Quicksort is O(n log n) usually, with an O(n²) worst case.
• Say "stable" when it matters. If a problem sorts by one field and cares about the order of ties, say that you need a stable sort, and name sort_by_key as one.
• Mention the lower bound. A sort that works by comparing items cannot beat O(n log n) in the worst case. Saying so shows you know where the limit comes from.
• Do not hand-write what the library does. In a real project, sort_by_key is the answer. In an interview, ask whether you may use it. If you are asked to write one, merge sort is the safest to get right.
• Count the cost of sorting first. If you sort and then do an O(n) pass, the answer is O(n log n), because the sort dominates. Say that out loud.
• Special values can skip the sort. A slice with only three possible values, like in problem 1, can be done in O(n). Look for small ranges before reaching for a general sort.

Made by VeraStack Labs