Step 4 of 7
Implementing sorts: insertion sort and merge sort
You'll almost never write a sort at work, since sort and sort_unstable are excellent. You'll write one in interviews, though, and the ideas behind these two show up everywhere: growing a sorted region, and divide and conquer.
Insertion sort
Keep the front of the slice sorted. Take the next item and swap it left until the item before it is not bigger. Like sorting a hand of cards.
fn insertion_sort(v: &mut [i32]) {
for i in 1..v.len() {
let mut j = i;
while j > 0 && v[j - 1] > v[j] {
v.swap(j - 1, j);
j -= 1;
}
println!("after pass {i}: {v:?}");
}
}
fn main() {
let mut v = [5, 2, 4, 6, 1, 3];
insertion_sort(&mut v);
}
after pass 1: [2, 5, 4, 6, 1, 3]
after pass 2: [2, 4, 5, 6, 1, 3]
after pass 3: [2, 4, 5, 6, 1, 3]
after pass 4: [1, 2, 4, 5, 6, 3]
after pass 5: [1, 2, 3, 4, 5, 6]
Worst case O(n²) (reverse-sorted input: every item travels all the way left), but only O(n) on data that's already nearly sorted, and very fast for tiny slices. It's stable (equal items never swap past each other) and in place (no extra memory). The standard library's sorts switch to insertion sort for small pieces.
Merge sort
Divide and conquer: split the problem in half, solve each half (recursively), combine the results.
- A slice of 0 or 1 items is already sorted (the base case).
- Otherwise split it in the middle with
split_at, merge sort each half. - Merge the two sorted halves: repeatedly take the smaller front item.
The merge is the heart of it, and it's useful on its own. Here it combines two log files that are each sorted by timestamp:
fn merge(a: &[u32], b: &[u32]) -> Vec<u32> {
let mut out = Vec::with_capacity(a.len() + b.len());
let (mut i, mut j) = (0, 0);
while i < a.len() && j < b.len() {
if a[i] <= b[j] {
out.push(a[i]);
i += 1;
} else {
out.push(b[j]);
j += 1;
}
}
out.extend_from_slice(&a[i..]); // whatever is left over
out.extend_from_slice(&b[j..]);
out
}
fn main() {
let web = [3, 8, 15, 21];
let db = [1, 8, 9, 30, 31];
println!("{:?}", merge(&web, &db));
}
[1, 3, 8, 8, 9, 15, 21, 30, 31]
Why O(n log n)? Halving n items until pieces have size 1 takes log₂ n levels, and each level merges all n items once. Merge sort is stable and always O(n log n), but needs O(n) extra memory for the merged output.
Quicksort is the other famous one: pick a pivot, move smaller items left of it and bigger ones right, then sort both sides. It works in place and is very fast on average, but O(n²) if the pivots are chosen badly. Rust's sort_unstable is a modern quicksort variant that guards against the bad cases.
Common mistakes
- A missing or unreachable base case. If a 1-item slice still gets split,
split_at(0)gives an empty half and the same 1-item half again, forever, until the program aborts withthread 'main' (4242) has overflowed its stack. - Forgetting the leftovers after the merge loop: one of the two slices still has items.
<instead of<=in the merge. Taking from the right half on ties still sorts, but it's no longer stable.
Your task
Write fn merge_sort(v: &[i32]) -> Vec<i32> that returns a sorted copy, using recursion, split_at and a merge function you write (adapt the one above to i32). No sort methods. The tests sort 200,000 numbers, which insertion sort would take minutes for.
Challenge 2
Make insertion sort generic: fn insertion_sort<T: PartialOrd>(v: &mut [T]) sorts any slice whose items can be compared, in place, using swap. It should work on numbers, floats and strings alike. No sort methods.
Challenge 3
A music app compares your ranking of songs with a friend's by counting inversions: pairs i < j where v[i] > v[j]. A sorted list has 0; a reversed list of n items has n(n-1)/2.
Write fn count_inversions(v: &[i32]) -> u64. Checking every pair is O(n²), and the tests use 100,000 numbers. Modify merge sort: while merging, every time you take an item from the right half, it's smaller than everything still waiting in the left half, so it forms one inversion with each of them (left.len() - i inversions at once). Have a recursive helper return both the sorted Vec and the count.