251 Intermediate

Quicksort

Sorting algorithms

Tutorial Video

Text description (accessibility)

This video demonstrates the "Quicksort" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Sorting algorithms. Sort a list of comparable elements using the quicksort algorithm: select a pivot, partition remaining elements into those less than and those greater-or-equal, recurse on each partition, then concatenate. Key difference from OCaml: 1. **Persistence vs mutation:** OCaml lists are immutable; functional Rust clones into new `Vec`s; idiomatic Rust sorts in place with `&mut [T]`.

Tutorial

The Problem

Sort a list of comparable elements using the quicksort algorithm: select a pivot, partition remaining elements into those less than and those greater-or-equal, recurse on each partition, then concatenate.

🎯 Learning Outcomes

• How Rust's slice pattern matching ([pivot, rest @ ..]) mirrors OCaml's list destructuring

• The Clone bound: when returning new allocations from borrowed input, values must be cloned

• Two valid quicksort styles — functional (allocating, like OCaml) vs in-place (Lomuto partition)

• Why idiomatic Rust prefers data.sort() over hand-rolled sorts for production code

🦀 The Rust Way

The functional translation uses slice patterns ([pivot, rest @ ..]) and .partition() on an iterator, producing Vec<T> values at each level. For production use, Rust's slice::sort (an introsort variant — hybrid quicksort/heapsort/insertion sort) is preferred. The in-place Lomuto scheme shows how Rust's mutable borrow splitting (&mut data[..k]) enables safe recursive in-place algorithms.

Code Example

pub fn quicksort<T: Ord + Clone>(list: &[T]) -> Vec<T> {
    match list {
        [] => vec![],
        [pivot, rest @ ..] => {
            let (left, right): (Vec<T>, Vec<T>) =
                rest.iter().cloned().partition(|x| x < pivot);
            let mut result = quicksort(&left);
            result.push(pivot.clone());
            result.extend(quicksort(&right));
            result
        }
    }
}

let rec quicksort = function
  | [] -> []
  | pivot :: rest ->
    let left, right = List.partition (fun x -> x < pivot) rest in
    quicksort left @ [pivot] @ quicksort right

Key Differences

Persistence vs mutation: OCaml lists are immutable; functional Rust clones into new Vecs; idiomatic Rust sorts in place with &mut [T].

Pattern syntax: OCaml pivot :: rest becomes Rust [pivot, rest @ ..] on slices.

**Clone requirement:** Rust must explicitly annotate T: Clone when cloning elements out of a borrowed slice; OCaml's GC handles this transparently.

Production sort: slice::sort is O(n log n) worst-case (introsort); the naïve functional quicksort is O(n²) on sorted input.

OCaml Approach

OCaml uses recursive list destructuring with a single pivot and List.partition to split the tail. The result is built by concatenating sorted sub-lists with @. Lists are persistent and immutable, so every call allocates new lists.

Full Source

#![allow(clippy::all)]
// Solution 1: Idiomatic Rust — uses slice::sort (in-place, introsort-based)
// This is how a Rust developer sorts: modify in place, no allocation per step
pub fn quicksort_inplace<T: Ord>(data: &mut [T]) {
    data.sort();
}

// Solution 2: Functional/recursive — mirrors the OCaml structure exactly
// Partition around a pivot, recurse on left and right, concatenate
// Takes &[T] and returns a new Vec<T> — allocation per call, like OCaml lists
pub fn quicksort<T: Ord + Clone>(list: &[T]) -> Vec<T> {
    match list {
        [] => vec![],
        [pivot, rest @ ..] => {
            let (left, right): (Vec<T>, Vec<T>) = rest.iter().cloned().partition(|x| x < pivot);
            let mut result = quicksort(&left);
            result.push(pivot.clone());
            result.extend(quicksort(&right));
            result
        }
    }
}

// Solution 3: In-place recursive quicksort — Lomuto partition scheme
// Shows the classic imperative algorithm Rust is well-suited for
pub fn quicksort_recursive<T: Ord>(data: &mut [T]) {
    if data.len() <= 1 {
        return;
    }
    let pivot_idx = partition(data);
    quicksort_recursive(&mut data[..pivot_idx]);
    quicksort_recursive(&mut data[pivot_idx + 1..]);
}

fn partition<T: Ord>(data: &mut [T]) -> usize {
    let last = data.len() - 1;
    let mut store = 0;
    for i in 0..last {
        if data[i] <= data[last] {
            data.swap(i, store);
            store += 1;
        }
    }
    data.swap(store, last);
    store
}

#[cfg(test)]
mod tests {
    use super::*;

    // --- quicksort (functional) ---

    #[test]
    fn test_functional_empty() {
        assert_eq!(quicksort::<i32>(&[]), vec![]);
    }

    #[test]
    fn test_functional_single() {
        assert_eq!(quicksort(&[42]), vec![42]);
    }

    #[test]
    fn test_functional_multiple() {
        assert_eq!(
            quicksort(&[3, 6, 8, 10, 1, 2, 1]),
            vec![1, 1, 2, 3, 6, 8, 10]
        );
    }

    #[test]
    fn test_functional_reversed() {
        assert_eq!(quicksort(&[5, 4, 3, 2, 1]), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_functional_already_sorted() {
        assert_eq!(quicksort(&[1, 2, 3, 4, 5]), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_functional_duplicates() {
        assert_eq!(quicksort(&[3, 3, 3]), vec![3, 3, 3]);
    }

    // --- quicksort_recursive (in-place Lomuto) ---

    #[test]
    fn test_recursive_empty() {
        let mut data: Vec<i32> = vec![];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![]);
    }

    #[test]
    fn test_recursive_single() {
        let mut data = vec![7];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![7]);
    }

    #[test]
    fn test_recursive_multiple() {
        let mut data = vec![3, 6, 8, 10, 1, 2, 1];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![1, 1, 2, 3, 6, 8, 10]);
    }

    #[test]
    fn test_recursive_reversed() {
        let mut data = vec![5, 4, 3, 2, 1];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![1, 2, 3, 4, 5]);
    }

    // --- quicksort_inplace (stdlib) ---

    #[test]
    fn test_inplace_sorts_correctly() {
        let mut data = vec![3, 6, 8, 10, 1, 2, 1];
        quicksort_inplace(&mut data);
        assert_eq!(data, vec![1, 1, 2, 3, 6, 8, 10]);
    }

    #[test]
    fn test_inplace_strings() {
        let mut data = vec!["banana", "apple", "cherry"];
        quicksort_inplace(&mut data);
        assert_eq!(data, vec!["apple", "banana", "cherry"]);
    }
}

let rec quicksort = function
  | [] -> []
  | pivot :: rest ->
    let left, right = List.partition (fun x -> x < pivot) rest in
    quicksort left @ [pivot] @ quicksort right

let () =
  let sorted = quicksort [3; 6; 8; 10; 1; 2; 1] in
  List.iter (Printf.printf "%d ") sorted;
  print_newline ();
  assert (quicksort [] = []);
  assert (quicksort [1] = [1]);
  assert (quicksort [3; 6; 8; 10; 1; 2; 1] = [1; 1; 2; 3; 6; 8; 10]);
  assert (quicksort [5; 4; 3; 2; 1] = [1; 2; 3; 4; 5]);
  print_endline "ok"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    // --- quicksort (functional) ---

    #[test]
    fn test_functional_empty() {
        assert_eq!(quicksort::<i32>(&[]), vec![]);
    }

    #[test]
    fn test_functional_single() {
        assert_eq!(quicksort(&[42]), vec![42]);
    }

    #[test]
    fn test_functional_multiple() {
        assert_eq!(
            quicksort(&[3, 6, 8, 10, 1, 2, 1]),
            vec![1, 1, 2, 3, 6, 8, 10]
        );
    }

    #[test]
    fn test_functional_reversed() {
        assert_eq!(quicksort(&[5, 4, 3, 2, 1]), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_functional_already_sorted() {
        assert_eq!(quicksort(&[1, 2, 3, 4, 5]), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_functional_duplicates() {
        assert_eq!(quicksort(&[3, 3, 3]), vec![3, 3, 3]);
    }

    // --- quicksort_recursive (in-place Lomuto) ---

    #[test]
    fn test_recursive_empty() {
        let mut data: Vec<i32> = vec![];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![]);
    }

    #[test]
    fn test_recursive_single() {
        let mut data = vec![7];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![7]);
    }

    #[test]
    fn test_recursive_multiple() {
        let mut data = vec![3, 6, 8, 10, 1, 2, 1];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![1, 1, 2, 3, 6, 8, 10]);
    }

    #[test]
    fn test_recursive_reversed() {
        let mut data = vec![5, 4, 3, 2, 1];
        quicksort_recursive(&mut data);
        assert_eq!(data, vec![1, 2, 3, 4, 5]);
    }

    // --- quicksort_inplace (stdlib) ---

    #[test]
    fn test_inplace_sorts_correctly() {
        let mut data = vec![3, 6, 8, 10, 1, 2, 1];
        quicksort_inplace(&mut data);
        assert_eq!(data, vec![1, 1, 2, 3, 6, 8, 10]);
    }

    #[test]
    fn test_inplace_strings() {
        let mut data = vec!["banana", "apple", "cherry"];
        quicksort_inplace(&mut data);
        assert_eq!(data, vec!["apple", "banana", "cherry"]);
    }
}

Deep Comparison

OCaml vs Rust: Quicksort

Side-by-Side Code

OCaml

let rec quicksort = function
  | [] -> []
  | pivot :: rest ->
    let left, right = List.partition (fun x -> x < pivot) rest in
    quicksort left @ [pivot] @ quicksort right

Rust (functional/recursive — mirrors OCaml)

pub fn quicksort<T: Ord + Clone>(list: &[T]) -> Vec<T> {
    match list {
        [] => vec![],
        [pivot, rest @ ..] => {
            let (left, right): (Vec<T>, Vec<T>) =
                rest.iter().cloned().partition(|x| x < pivot);
            let mut result = quicksort(&left);
            result.push(pivot.clone());
            result.extend(quicksort(&right));
            result
        }
    }
}

Rust (in-place recursive — Lomuto partition scheme)

pub fn quicksort_recursive<T: Ord>(data: &mut [T]) {
    if data.len() <= 1 { return; }
    let pivot_idx = partition(data);
    quicksort_recursive(&mut data[..pivot_idx]);
    quicksort_recursive(&mut data[pivot_idx + 1..]);
}

fn partition<T: Ord>(data: &mut [T]) -> usize {
    let last = data.len() - 1;
    let mut store = 0;
    for i in 0..last {
        if data[i] <= data[last] {
            data.swap(i, store);
            store += 1;
        }
    }
    data.swap(store, last);
    store
}

Rust (idiomatic — stdlib introsort)

pub fn quicksort_inplace<T: Ord>(data: &mut [T]) {
    data.sort();
}

Type Signatures

Concept	OCaml	Rust
Functional sort	`val quicksort : 'a list -> 'a list`	`fn quicksort<T: Ord + Clone>(list: &[T]) -> Vec<T>`
In-place sort	N/A (immutable lists)	`fn quicksort_recursive<T: Ord>(data: &mut [T])`
List/slice type	`'a list`	`&[T]` (slice) or `Vec<T>`
Partition result	`'a list * 'a list`	`(Vec<T>, Vec<T>)`
Comparability	`'a` with polymorphic `<`	`T: Ord` (explicit trait bound)

Key Insights

List head destructuring: OCaml's pivot :: rest maps directly to Rust's [pivot, rest @ ..] slice pattern — both bind the first element and the remainder in a single match arm.

**Clone is explicit:** OCaml's GC lets the runtime share or copy values transparently. Rust requires T: Clone in the signature and explicit .cloned() / .clone() calls, making allocation visible at the type level.

Allocation model: Every OCaml recursive call produces new list nodes implicitly. The Rust functional version makes the same allocation pattern explicit with Vec<T>. The in-place Lomuto variant eliminates per-call allocation entirely by splitting &mut [T] borrows.

Borrow splitting for safe recursion: &mut data[..pivot_idx] and &mut data[pivot_idx + 1..] are non-overlapping mutable borrows — the borrow checker verifies this statically. OCaml has no equivalent concept; mutation would require ref or mutable records.

Production choice: Rust's slice::sort is an introsort (quicksort + heapsort fallback + insertion sort for small slices), giving O(n log n) worst-case. The naïve functional quicksort degrades to O(n²) on already-sorted input when always picking the first element as pivot.

When to Use Each Style

**Use idiomatic Rust (data.sort()) when:** sorting in production code where correctness and performance are paramount — it is cache-friendly, allocation-free, and O(n log n) worst-case.

**Use functional Rust (quicksort) when:** teaching the OCaml→Rust translation, demonstrating slice patterns and iterator-based partitioning, or when you need to return a new sorted copy without mutating the input.

**Use in-place recursive Rust (quicksort_recursive) when:** studying how Rust's borrow checker enables safe recursive mutation through non-overlapping slice splits, or implementing custom partition strategies.

Exercises

Implement a three-way partition quicksort (Dutch national flag) that handles equal elements efficiently and benchmarks better on lists with many duplicates.

Write an in-place functional-style quicksort using only safe Rust (no unsafe) with an explicit stack to avoid recursion.

Implement an introselect algorithm that uses quicksort's partition to find the k-th smallest element in expected O(n), then compare its performance to fully sorting the list.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust