Insertion Sort
Sorting Algorithms
Tutorial Video
Text description (accessibility)
This video demonstrates the "Insertion Sort" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Sorting Algorithms. Build a sorted list by inserting each element of an unsorted list into the correct position of an already-sorted accumulator, repeating until all elements are placed. Key difference from OCaml: 1. **Mutation model:** OCaml constructs new lists at every step; Rust's idiomatic version mutates a single `Vec` in place.
Tutorial
The Problem
Build a sorted list by inserting each element of an unsorted list into the correct position of an already-sorted accumulator, repeating until all elements are placed.
🎯 Learning Outcomes
fold_left replaces explicit loops: the OCaml pattern List.fold_left (fun acc x -> insert x acc) [] maps directly to Rust's .fold(Vec::new(), |acc, x| ...)data.swap() approach is zero-allocation; the functional approach allocates a new Vec per insertionslice::partition_point as a binary-search replacement for OCaml's linear scan through a sorted list[h, rest @ ..]) as a direct translation of OCaml's h :: t patterns🦀 The Rust Way
Three implementations show the spectrum. The idiomatic in-place version uses two nested index loops with slice::swap — zero allocation, cache-friendly, matching Rust's strengths. The functional version uses .fold with Vec::insert after a partition_point binary search, preserving the OCaml fold shape. The recursive version translates insert almost word-for-word using slice pattern matching.
Code Example
pub fn insertion_sort_inplace<T: Ord>(data: &mut [T]) {
for i in 1..data.len() {
let mut j = i;
while j > 0 && data[j - 1] > data[j] {
data.swap(j - 1, j);
j -= 1;
}
}
}Key Differences
Vec in place.h :: t destructuring becomes Rust's [h, rest @ ..] slice pattern — same idea, different syntax.insert scans linearly; Rust's functional version uses partition_point (binary search) on the sorted accumulator for O(log n) comparisons.x <= h guard and Rust's partition_point(|h| h < &x) place equal elements in original order — both sorts are stable.OCaml Approach
OCaml defines a recursive insert that pattern-matches on the list head: if x <= h the element is prepended before h; otherwise h is kept and the recursion continues into the tail. insertion_sort folds this inserter over an empty accumulator, building the result purely through list construction without mutation.
Full Source
#![allow(clippy::all)]
// Solution 1: Idiomatic Rust — in-place insertion sort using slice swaps
// How a Rust developer writes it: mutate in place, no allocation per step
pub fn insertion_sort_inplace<T: Ord>(data: &mut [T]) {
for i in 1..data.len() {
let mut j = i;
while j > 0 && data[j - 1] > data[j] {
data.swap(j - 1, j);
j -= 1;
}
}
}
// Solution 2: Functional — mirrors the OCaml fold structure exactly
// `List.fold_left (fun acc x -> insert x acc) [] lst`
// Uses partition_point for O(log n) search within the O(n) insert
pub fn insertion_sort_functional<T: Ord + Clone>(list: &[T]) -> Vec<T> {
list.iter().cloned().fold(Vec::new(), |mut acc, x| {
// Insert x before the first element strictly greater than x.
// OCaml: `if x <= h then x :: l` — x goes before h when x <= h,
// meaning x goes after all elements < x (stable, left-biased).
let pos = acc.partition_point(|h| h < &x);
acc.insert(pos, x);
acc
})
}
// Solution 3: Recursive — explicit recursion mirroring OCaml's `insert` function
// `let rec insert x = function | [] -> [x] | h :: t as l -> if x <= h then x :: l else h :: insert x t`
pub fn insert_rec<T: Ord + Clone>(x: T, list: &[T]) -> Vec<T> {
match list {
[] => vec![x],
[h, rest @ ..] => {
if x <= *h {
let mut result = vec![x];
result.extend_from_slice(list);
result
} else {
let mut result = vec![h.clone()];
result.extend(insert_rec(x, rest));
result
}
}
}
}
pub fn insertion_sort_recursive<T: Ord + Clone>(list: &[T]) -> Vec<T> {
list.iter()
.cloned()
.fold(Vec::new(), |acc, x| insert_rec(x, &acc))
}
#[cfg(test)]
mod tests {
use super::*;
// --- insertion_sort_inplace ---
#[test]
fn test_inplace_empty() {
let mut data: Vec<i32> = vec![];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![]);
}
#[test]
fn test_inplace_single() {
let mut data = vec![42];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![42]);
}
#[test]
fn test_inplace_multiple() {
let mut data = vec![5, 3, 1, 4, 2];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_inplace_already_sorted() {
let mut data = vec![1, 2, 3, 4, 5];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_inplace_reversed() {
let mut data = vec![5, 4, 3, 2, 1];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_inplace_duplicates() {
let mut data = vec![3, 1, 4, 1, 5, 9, 2, 6];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 1, 2, 3, 4, 5, 6, 9]);
}
// --- insertion_sort_functional ---
#[test]
fn test_functional_empty() {
assert_eq!(insertion_sort_functional::<i32>(&[]), vec![]);
}
#[test]
fn test_functional_single() {
assert_eq!(insertion_sort_functional(&[7]), vec![7]);
}
#[test]
fn test_functional_multiple() {
assert_eq!(
insertion_sort_functional(&[5, 3, 1, 4, 2]),
vec![1, 2, 3, 4, 5]
);
}
#[test]
fn test_functional_duplicates() {
assert_eq!(
insertion_sort_functional(&[3, 1, 4, 1, 5]),
vec![1, 1, 3, 4, 5]
);
}
// --- insertion_sort_recursive ---
#[test]
fn test_recursive_empty() {
assert_eq!(insertion_sort_recursive::<i32>(&[]), vec![]);
}
#[test]
fn test_recursive_single() {
assert_eq!(insertion_sort_recursive(&[99]), vec![99]);
}
#[test]
fn test_recursive_multiple() {
assert_eq!(
insertion_sort_recursive(&[5, 3, 1, 4, 2]),
vec![1, 2, 3, 4, 5]
);
}
#[test]
fn test_recursive_strings() {
assert_eq!(
insertion_sort_recursive(&["banana", "apple", "cherry"]),
vec!["apple", "banana", "cherry"]
);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
// --- insertion_sort_inplace ---
#[test]
fn test_inplace_empty() {
let mut data: Vec<i32> = vec![];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![]);
}
#[test]
fn test_inplace_single() {
let mut data = vec![42];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![42]);
}
#[test]
fn test_inplace_multiple() {
let mut data = vec![5, 3, 1, 4, 2];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_inplace_already_sorted() {
let mut data = vec![1, 2, 3, 4, 5];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_inplace_reversed() {
let mut data = vec![5, 4, 3, 2, 1];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_inplace_duplicates() {
let mut data = vec![3, 1, 4, 1, 5, 9, 2, 6];
insertion_sort_inplace(&mut data);
assert_eq!(data, vec![1, 1, 2, 3, 4, 5, 6, 9]);
}
// --- insertion_sort_functional ---
#[test]
fn test_functional_empty() {
assert_eq!(insertion_sort_functional::<i32>(&[]), vec![]);
}
#[test]
fn test_functional_single() {
assert_eq!(insertion_sort_functional(&[7]), vec![7]);
}
#[test]
fn test_functional_multiple() {
assert_eq!(
insertion_sort_functional(&[5, 3, 1, 4, 2]),
vec![1, 2, 3, 4, 5]
);
}
#[test]
fn test_functional_duplicates() {
assert_eq!(
insertion_sort_functional(&[3, 1, 4, 1, 5]),
vec![1, 1, 3, 4, 5]
);
}
// --- insertion_sort_recursive ---
#[test]
fn test_recursive_empty() {
assert_eq!(insertion_sort_recursive::<i32>(&[]), vec![]);
}
#[test]
fn test_recursive_single() {
assert_eq!(insertion_sort_recursive(&[99]), vec![99]);
}
#[test]
fn test_recursive_multiple() {
assert_eq!(
insertion_sort_recursive(&[5, 3, 1, 4, 2]),
vec![1, 2, 3, 4, 5]
);
}
#[test]
fn test_recursive_strings() {
assert_eq!(
insertion_sort_recursive(&["banana", "apple", "cherry"]),
vec!["apple", "banana", "cherry"]
);
}
}Deep Comparison
OCaml vs Rust: Insertion Sort
Side-by-Side Code
OCaml
let rec insert x = function
| [] -> [x]
| h :: t as l ->
if x <= h then x :: l
else h :: insert x t
let insertion_sort lst =
List.fold_left (fun acc x -> insert x acc) [] lst
Rust (idiomatic — in-place)
pub fn insertion_sort_inplace<T: Ord>(data: &mut [T]) {
for i in 1..data.len() {
let mut j = i;
while j > 0 && data[j - 1] > data[j] {
data.swap(j - 1, j);
j -= 1;
}
}
}
Rust (functional — fold + partition_point)
pub fn insertion_sort_functional<T: Ord + Clone>(list: &[T]) -> Vec<T> {
list.iter().cloned().fold(Vec::new(), |mut acc, x| {
let pos = acc.partition_point(|h| h < &x);
acc.insert(pos, x);
acc
})
}
Rust (recursive — mirrors OCaml's insert)
pub fn insert_rec<T: Ord + Clone>(x: T, list: &[T]) -> Vec<T> {
match list {
[] => vec![x],
[h, rest @ ..] => {
if x <= *h {
let mut result = vec![x];
result.extend_from_slice(list);
result
} else {
let mut result = vec![h.clone()];
result.extend(insert_rec(x, rest));
result
}
}
}
}
pub fn insertion_sort_recursive<T: Ord + Clone>(list: &[T]) -> Vec<T> {
list.iter()
.cloned()
.fold(Vec::new(), |acc, x| insert_rec(x, &acc))
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| Insert function | val insert : 'a -> 'a list -> 'a list | fn insert_rec<T: Ord + Clone>(x: T, list: &[T]) -> Vec<T> |
| Sort (functional) | val insertion_sort : 'a list -> 'a list | fn insertion_sort_functional<T: Ord + Clone>(list: &[T]) -> Vec<T> |
| Sort (in-place) | (not idiomatic in OCaml) | fn insertion_sort_inplace<T: Ord>(data: &mut [T]) |
| List/slice type | 'a list | &[T] (borrow) / Vec<T> (owned) |
| Ordering constraint | (compare : 'a -> 'a -> int) implicit | T: Ord explicit trait bound |
Key Insights
fold_left is Iterator::fold:** OCaml's List.fold_left f init lst is exactly .fold(init, f) on a Rust iterator. The pattern transfers verbatim — only the argument order inside the closure differs slightly.| h :: t as l -> becomes [h, rest @ ..] in Rust. Rust requires the full list to be a slice (&[T]), not a linked list, but the syntactic parallel is close enough to read as a direct translation.partition_point replaces linear scan:** OCaml's insert walks the list element by element. Rust's sorted Vec supports partition_point (binary search on a predicate), reducing comparisons from O(n) to O(log n). The overall sort is still O(n²) due to Vec::insert shifting, but search is faster.x <= h keeps the new x to the left; Rust's partition_point(|h| h < &x) finds the position after all h < x, so ties also land before existing equal elements.x :: l and h :: insert x t allocates a new cons cell — allocation is unavoidable. Rust's in-place version allocates a single Vec upfront and mutates it, making it O(1) space overhead. The functional Rust version mimics OCaml and allocates per call.When to Use Each Style
**Use idiomatic in-place (insertion_sort_inplace) when:** you own the data, care about performance, and want zero extra allocation. Rust's ownership model makes in-place mutation safe and idiomatic.
**Use functional fold (insertion_sort_functional) when:** you want a pure function that returns a new sorted collection without modifying the input — matching OCaml's immutable style or when the caller must retain the original slice.
**Use recursive (insertion_sort_recursive) when:** teaching or demonstrating the direct OCaml→Rust translation, or when the recursive structure itself is the subject of study. Avoid for production use on large inputs due to stack depth and repeated allocations.
Exercises
Vec<Option<usize>> (next-pointer encoding) in-place by relinking pointers instead of moving values.sort for small arrays (n ≤ 16) and explain why std's Timsort uses insertion sort as a base case.