12 — Divide and Conquer

What is Divide and Conquer?

1. Divide problem into smaller subproblems
2. Conquer subproblems recursively
3. Combine results

           Problem
          /       \
     Sub-1         Sub-2
     /   \         /   \
   S-1a  S-1b   S-2a  S-2b
    ↓     ↓      ↓     ↓
  solve  solve  solve  solve
    \     /      \     /
   combine      combine
       \          /
        combine

---

Merge Sort — Analysis

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  while (i < a.length) result.push(a[i++]);
  while (j < b.length) result.push(b[j++]);
  return result;
}

Time: T(n) = 2T(n/2) + O(n) → O(n log n) (always) Space: O(n) for merge buffer

Count Inversions (merge sort variant)

function countInversions(arr: number[]): number {
  let count = 0;
  
  function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    const mid = arr.length >> 1;
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return mergeCount(left, right);
  }
  
  function mergeCount(a: number[], b: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;
    while (i < a.length && j < b.length) {
      if (a[i] <= b[j]) {
        result.push(a[i++]);
      } else {
        count += a.length - i; // All remaining in left are > b[j]
        result.push(b[j++]);
      }
    }
    while (i < a.length) result.push(a[i++]);
    while (j < b.length) result.push(b[j++]);
    return result;
  }
  
  mergeSort(arr);
  return count;
}

---

Quick Select — K-th Element

Find k-th smallest in O(n) average.

function quickSelect(arr: number[], k: number): number {
  // k is 1-indexed
  function select(lo: number, hi: number): number {
    const pivot = arr[hi];
    let i = lo;
    
    for (let j = lo; j < hi; j++) {
      if (arr[j] <= pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }
    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    
    if (i === k - 1) return arr[i];
    if (i > k - 1) return select(lo, i - 1);
    return select(i + 1, hi);
  }
  
  return select(0, arr.length - 1);
}

// Average O(n), worst O(n²) — randomize pivot for better guarantee

---

Closest Pair of Points

// Find minimum distance between any two points
// Brute force: O(n²) | D&C: O(n log n)
function closestPair(points: [number, number][]): number {
  points.sort((a, b) => a[0] - b[0]); // Sort by x
  
  function dist(a: [number, number], b: [number, number]): number {
    return Math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2);
  }
  
  function solve(pts: [number, number][]): number {
    if (pts.length <= 3) {
      let min = Infinity;
      for (let i = 0; i < pts.length; i++)
        for (let j = i + 1; j < pts.length; j++)
          min = Math.min(min, dist(pts[i], pts[j]));
      return min;
    }
    
    const mid = pts.length >> 1;
    const midX = pts[mid][0];
    const left = solve(pts.slice(0, mid));
    const right = solve(pts.slice(mid));
    let d = Math.min(left, right);
    
    // Check strip around midline
    const strip = pts.filter(p => Math.abs(p[0] - midX) < d);
    strip.sort((a, b) => a[1] - b[1]); // Sort by y
    
    for (let i = 0; i < strip.length; i++) {
      for (let j = i + 1; j < strip.length && strip[j][1] - strip[i][1] < d; j++) {
        d = Math.min(d, dist(strip[i], strip[j]));
      }
    }
    return d;
  }
  
  return solve(points);
}

---

Master Theorem

For recurrences of the form: T(n) = aT(n/b) + O(n^d)

Examples:

---

Key Takeaways

• D&C splits problem, solves independently, merges — works when subproblems don't overlap
• Merge sort: O(n log n) always; variant counts inversions
• Quick select: O(n) average for k-th element; randomize pivot
• Closest pair: O(n log n) by splitting on x-coordinate + strip check
• Master theorem: quick way to solve D&C recurrences — memorize the 3 cases