840 Fundamental

Divide and Conquer Pattern

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Divide and Conquer Pattern" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Divide and conquer is an algorithm design paradigm that decomposes a problem into smaller independent subproblems, solves them recursively, and combines solutions. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Divide and conquer is an algorithm design paradigm that decomposes a problem into smaller independent subproblems, solves them recursively, and combines solutions. It underlies merge sort, quicksort, binary search, FFT, Strassen matrix multiplication, and closest pair of points. The recurrence T(n) = aT(n/b) + f(n) is analyzed by the Master Theorem. Understanding divide and conquer as a pattern — not just specific algorithms — enables recognizing and applying it to new problems. Many problems that appear to require O(n^2) naive solutions admit O(n log n) or better divide-and-conquer solutions.

🎯 Learning Outcomes

• Identify the three components: divide (split problem), conquer (recursive solve), combine (merge solutions)

• Apply Master Theorem to analyze recurrences: T(n) = aT(n/b) + O(n^k)

• Implement generic divide-and-conquer scaffolding with configurable split, solve, and merge operations

• Recognize when divide-and-conquer helps: independent subproblems with efficient merge

• Compare with dynamic programming: D&C has independent subproblems; DP has overlapping ones

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Divide and Conquer Framework in OCaml *)

(* Merge sort — the canonical D&C algorithm *)
let rec merge_sort (xs : 'a list) : 'a list =
  match xs with
  | [] | [_] -> xs
  | _ ->
    let n = List.length xs in
    let mid = n / 2 in
    let left = List.filteri (fun i _ -> i < mid) xs in
    let right = List.filteri (fun i _ -> i >= mid) xs in
    let sl = merge_sort left in
    let sr = merge_sort right in
    (* Merge two sorted lists *)
    let rec merge a b = match (a, b) with
      | ([], b) -> b
      | (a, []) -> a
      | (x::xs, y::ys) ->
        if x <= y then x :: merge xs b
        else y :: merge a ys
    in
    merge sl sr

(* Binary search: returns Some index or None *)
let binary_search (arr : 'a array) (target : 'a) : int option =
  let rec go lo hi =
    if lo > hi then None
    else
      let mid = (lo + hi) / 2 in
      if arr.(mid) = target then Some mid
      else if arr.(mid) < target then go (mid + 1) hi
      else go lo (mid - 1)
  in
  go 0 (Array.length arr - 1)

(* Maximum subarray sum via D&C (Kadane's is O(n) but D&C shows the pattern) *)
let max_crossing_sum (arr : int array) (lo mid hi : int) : int =
  let left_sum = ref min_int and s = ref 0 in
  for i = mid downto lo do
    s := !s + arr.(i);
    if !s > !left_sum then left_sum := !s
  done;
  let right_sum = ref min_int in
  s := 0;
  for i = mid + 1 to hi do
    s := !s + arr.(i);
    if !s > !right_sum then right_sum := !s
  done;
  !left_sum + !right_sum

let rec max_subarray (arr : int array) (lo hi : int) : int =
  if lo = hi then arr.(lo)
  else
    let mid = (lo + hi) / 2 in
    let left_max = max_subarray arr lo mid in
    let right_max = max_subarray arr (mid + 1) hi in
    let cross_max = max_crossing_sum arr lo mid hi in
    max left_max (max right_max cross_max)

let () =
  let xs = [5; 3; 8; 1; 9; 2; 7; 4; 6] in
  let sorted = merge_sort xs in
  Printf.printf "merge_sort %s = %s\n"
    (String.concat "," (List.map string_of_int xs))
    (String.concat "," (List.map string_of_int sorted));

  let arr = [| 1; 3; 5; 7; 9; 11; 13 |] in
  Printf.printf "binary_search(7) = %s\n"
    (match binary_search arr 7 with Some i -> string_of_int i | None -> "None");
  Printf.printf "binary_search(6) = %s\n"
    (match binary_search arr 6 with Some i -> string_of_int i | None -> "None");

  let nums = [| -2; 1; -3; 4; -1; 2; 1; -5; 4 |] in
  Printf.printf "max_subarray([-2,1,-3,4,-1,2,1,-5,4]) = %d (expected 6)\n"
    (max_subarray nums 0 (Array.length nums - 1))

Key Differences

Aspect	Rust	OCaml
Generic params	`<T, R, F, G, H>` with trait bounds	Polymorphic `'a -> 'b`
Function passing	References to closures	First-class functions
Array splitting	Slice references `&[T]`	`Array.sub` copies
Parallelism	`rayon::join`	`Domain.spawn` (OCaml 5.0)
Tail recursion	Not applicable (tree recursion)	Not TCO here
Pattern recognition	Master Theorem	Same analysis

OCaml Approach

OCaml's higher-order functions make the D&C pattern elegant: let rec dc base_case divide combine items = if small items then base_case items else let (l, r) = divide items in combine (dc base_case divide combine l) (dc base_case divide combine r). The divide_and_conquer function is naturally polymorphic. OCaml's Array.sub for splitting and @ or Array.append for combining arrays. The parallel version uses Domain.spawn (OCaml 5.0) to run both halves concurrently.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Divide and Conquer Framework in OCaml *)

(* Merge sort — the canonical D&C algorithm *)
let rec merge_sort (xs : 'a list) : 'a list =
  match xs with
  | [] | [_] -> xs
  | _ ->
    let n = List.length xs in
    let mid = n / 2 in
    let left = List.filteri (fun i _ -> i < mid) xs in
    let right = List.filteri (fun i _ -> i >= mid) xs in
    let sl = merge_sort left in
    let sr = merge_sort right in
    (* Merge two sorted lists *)
    let rec merge a b = match (a, b) with
      | ([], b) -> b
      | (a, []) -> a
      | (x::xs, y::ys) ->
        if x <= y then x :: merge xs b
        else y :: merge a ys
    in
    merge sl sr

(* Binary search: returns Some index or None *)
let binary_search (arr : 'a array) (target : 'a) : int option =
  let rec go lo hi =
    if lo > hi then None
    else
      let mid = (lo + hi) / 2 in
      if arr.(mid) = target then Some mid
      else if arr.(mid) < target then go (mid + 1) hi
      else go lo (mid - 1)
  in
  go 0 (Array.length arr - 1)

(* Maximum subarray sum via D&C (Kadane's is O(n) but D&C shows the pattern) *)
let max_crossing_sum (arr : int array) (lo mid hi : int) : int =
  let left_sum = ref min_int and s = ref 0 in
  for i = mid downto lo do
    s := !s + arr.(i);
    if !s > !left_sum then left_sum := !s
  done;
  let right_sum = ref min_int in
  s := 0;
  for i = mid + 1 to hi do
    s := !s + arr.(i);
    if !s > !right_sum then right_sum := !s
  done;
  !left_sum + !right_sum

let rec max_subarray (arr : int array) (lo hi : int) : int =
  if lo = hi then arr.(lo)
  else
    let mid = (lo + hi) / 2 in
    let left_max = max_subarray arr lo mid in
    let right_max = max_subarray arr (mid + 1) hi in
    let cross_max = max_crossing_sum arr lo mid hi in
    max left_max (max right_max cross_max)

let () =
  let xs = [5; 3; 8; 1; 9; 2; 7; 4; 6] in
  let sorted = merge_sort xs in
  Printf.printf "merge_sort %s = %s\n"
    (String.concat "," (List.map string_of_int xs))
    (String.concat "," (List.map string_of_int sorted));

  let arr = [| 1; 3; 5; 7; 9; 11; 13 |] in
  Printf.printf "binary_search(7) = %s\n"
    (match binary_search arr 7 with Some i -> string_of_int i | None -> "None");
  Printf.printf "binary_search(6) = %s\n"
    (match binary_search arr 6 with Some i -> string_of_int i | None -> "None");

  let nums = [| -2; 1; -3; 4; -1; 2; 1; -5; 4 |] in
  Printf.printf "max_subarray([-2,1,-3,4,-1,2,1,-5,4]) = %d (expected 6)\n"
    (max_subarray nums 0 (Array.length nums - 1))

Deep Comparison

OCaml vs Rust: Divide And Conquer Pattern

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement merge sort using the divide_and_conquer generic function with appropriate divide and combine closures.

Implement binary search as a divide-and-conquer: divide splits at midpoint, combine picks the recursive result.

Apply divide and conquer to count inversions in an array in O(n log n) by modifying merge sort.

Parallelize the divide step using Rayon's join and measure speedup on merge sort for n = 10^7.

Implement the divide-and-conquer closest pair using the generic scaffolding above with appropriate functions.

Open Source Repos

functional-rust

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

Rust