1123-sorting-algorithmsquicksort — Quicksort

Functional Programming

Tutorial

The Problem

Quicksort, invented by Tony Hoare in 1959, is the most widely used sorting algorithm in practice. It achieves O(n log n) average-case time by partitioning around a pivot: elements less than the pivot go left, greater go right, and the sub-arrays are recursively sorted. The in-place variant is cache-friendly and uses O(log n) stack space.

Understanding quicksort deepens understanding of divide-and-conquer, average-case analysis, pivot selection strategies, and why Rust's sort_unstable (which uses a quicksort variant) is faster than sort (which guarantees stability using merge sort).

🎯 Learning Outcomes

• Implement in-place quicksort using Lomuto or Hoare partition scheme

• Understand pivot selection and its effect on worst-case behavior

• Know why O(n²) worst case occurs (sorted input with naive pivot)

• Compare quicksort to merge sort: average O(n log n) vs worst-case O(n log n)

• Understand why Rust's sort_unstable uses a pattern-defeating quicksort (pdqsort)

Code Example

#![allow(clippy::all)]
//! Stub to satisfy cargo.
pub fn stub() {}

let rec quicksort gt = function
  | [] -> []
  | x::xs ->
      let ys, zs = List.partition (gt x) xs in
      (quicksort gt ys) @ (x :: (quicksort gt zs))
 
let _ =
  quicksort (>) [4; 65; 2; -31; 0; 99; 83; 782; 1]

Key Differences

In-place vs functional: Rust's in-place quicksort uses O(log n) stack space; OCaml's functional version uses O(n) space per level for list copies.

Stable sort: Rust's sort is stable (merge sort based); sort_unstable (quicksort based) is faster. OCaml's List.sort is stable (merge sort).

pdqsort: Rust's standard library uses pdqsort which handles sorted, reverse-sorted, and many-duplicates inputs in O(n) — better than naive quicksort.

Pivot selection: Both naive implementations use the last element as pivot; median-of-three and random pivots reduce worst-case probability.

OCaml Approach

let rec quicksort = function
  | [] -> []
  | pivot :: rest ->
    let smaller = List.filter (fun x -> x <= pivot) rest in
    let larger = List.filter (fun x -> x > pivot) rest in
    quicksort smaller @ [pivot] @ quicksort larger

This functional quicksort is elegant but O(n) space per level (allocates new lists at each step). For OCaml arrays, an in-place variant uses the same Lomuto/Hoare partitioning as Rust.

Full Source

#![allow(clippy::all)]
//! Stub to satisfy cargo.
pub fn stub() {}

let rec quicksort gt = function
  | [] -> []
  | x::xs ->
      let ys, zs = List.partition (gt x) xs in
      (quicksort gt ys) @ (x :: (quicksort gt zs))
 
let _ =
  quicksort (>) [4; 65; 2; -31; 0; 99; 83; 782; 1]

Exercises

Implement quicksort with median-of-three pivot selection and benchmark it against the last-element pivot on sorted input.

Write a three-way partition (Dutch National Flag) that handles many duplicate elements efficiently.

Implement par_quicksort(arr: &mut [i32]) using rayon for parallel sorting of the two sub-arrays.

Open Source Repos

functional-rust

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

Rust