252: Insertion Sort

Difficulty: 1 Level: Beginner Build a sorted list by inserting each element into its correct position in an already-sorted accumulator.

The Problem This Solves

Insertion sort is the algorithm you naturally use when sorting a hand of playing cards: you pick up one card at a time and slide it left until it's in the right place. It's simple to understand, stable (equal elements keep their original order), and efficient for nearly-sorted data. Beyond the algorithm itself, this example is a tour of how OCaml's functional patterns translate to Rust. OCaml's `List.fold_left` becomes Rust's `.fold()`. OCaml's `h :: t` list destructuring becomes Rust's `[h, rest @ ..]` slice patterns. OCaml's linear scan for insertion position becomes Rust's `partition_point` binary search — same semantics, better performance. The example shows three styles: idiomatic in-place Rust (fastest, zero allocation), functional fold (mirrors OCaml), and recursive (word-for-word translation of OCaml's `insert` function). Comparing them reveals what Rust's ownership model adds.

The Intuition

Start with an empty sorted list. Take the first element from the unsorted input and insert it — into an empty list, it goes first. Take the second element and find the right spot: scan left-to-right, stop when you find a larger element, insert there. Repeat until all elements are placed. The insert step is the core: given a sorted list and a new element `x`, find the first position where the existing element `h >= x`, and slot `x` in just before `h`. If `x` is larger than everything, it goes at the end. OCaml's `insert` function does this recursively: if `x <= head`, prepend `x`; otherwise keep the head and recurse into the tail. Rust can express this as slice pattern matching — `[h, rest @ ..]` is exactly `h :: rest`.

How It Works in Rust

// Style 1: Idiomatic — in-place, zero allocation
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);  // bubble left until in place
         j -= 1;
     }
 }
}

// Style 2: Functional — mirrors OCaml's fold structure
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); // binary search for insert pos
     acc.insert(pos, x);
     acc
 })
}

// Style 3: Recursive — direct translation of 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];  // x goes before h
             result.extend_from_slice(list);
             result
         } else {
             let mut result = vec![h.clone()];
             result.extend(insert_rec(x, rest)); // recurse into tail
             result
         }
     }
 }
}

What This Unlocks

Slice pattern matching — `[h, rest @ ..]` is idiomatic Rust for head/tail decomposition; use it in parsers, recursive algorithms, and data processing.
`partition_point` as a search primitive — binary search for insertion position; applicable anywhere you maintain a sorted `Vec`.
Fold for accumulation — the `.fold(Vec::new(), |acc, x| ...)` pattern builds any accumulator from an iterator; generalises far beyond sorting.

Key Differences

Concept	OCaml	Rust
List head access	`h :: t` (cons pattern)	`[h, rest @ ..]` (slice pattern)
Fold accumulation	`List.fold_left (fun acc x -> ...) []`	`.fold(Vec::new(), \	acc, x\	...)`
Insert position	Linear scan: `if x <= h`	`partition_point` binary search — O(log n)
In-place sorting	Not idiomatic (immutable lists)	`slice::swap` — zero allocation
Stability	Stable (`x <= h` preserves order)	Stable (same condition)

// Solution 1: Idiomatic Rust — in-place insertion sort using slice swaps
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 OCaml's fold structure
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
    })
}

// Solution 3: Recursive — mirrors OCaml's `insert` function
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))
}

fn main() {
    let input = [5, 3, 1, 4, 2];

    // In-place
    let mut data = input;
    insertion_sort_inplace(&mut data);
    println!("inplace:    {:?}", data);

    // Functional fold
    let sorted = insertion_sort_functional(&input);
    println!("functional: {:?}", sorted);

    // Recursive
    let sorted = insertion_sort_recursive(&input);
    println!("recursive:  {:?}", sorted);

    // Works on strings too
    let words = ["banana", "apple", "cherry", "date"];
    println!("strings:    {:?}", insertion_sort_functional(&words));
}

/* Output:
   inplace:    [1, 2, 3, 4, 5]
   functional: [1, 2, 3, 4, 5]
   recursive:  [1, 2, 3, 4, 5]
   strings:    ["apple", "banana", "cherry", "date"]
*/

(* Idiomatic OCaml — insert x into a sorted list, then fold *)
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

(* Recursive variant that makes the fold explicit *)
let rec insertion_sort_rec = function
  | [] -> []
  | x :: rest -> insert x (insertion_sort_rec rest)

let () =
  assert (insertion_sort [5; 3; 1; 4; 2] = [1; 2; 3; 4; 5]);
  assert (insertion_sort [] = []);
  assert (insertion_sort [1] = [1]);
  assert (insertion_sort [3; 1; 4; 1; 5] = [1; 1; 3; 4; 5]);
  assert (insertion_sort_rec [5; 3; 1; 4; 2] = [1; 2; 3; 4; 5]);
  print_endline "ok"

📊 Detailed Comparison

OCaml vs Rust: Insertion Sort

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

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

1. `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.

2. Slice patterns replace list patterns: OCaml's `| 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.

3. `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.

4. Stability from the comparison guard: Both versions are stable because equal elements are inserted before existing equals. OCaml's `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.

5. Allocation model — functional vs. in-place: OCaml lists are singly-linked and immutable, so every `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.