20. Divide & Conquer

TL;DR

Split the instance into disjoint subinstances of roughly half size, recurse until trivial bases, then merge or combine results—merge sort (stable divide + linear merge), quicksort (partition around pivot then recurse), binary search (one branch only, depth (O(\log n))). Advanced structures like segment trees recurse on index ranges to answer range queries in (O(\log n)) per query after (O(n)) build. Master theorem (one line): for (T(n) = a,T(n/b) + O(n^d)), compare (a) with (b^d): if (a > b^d) then (O(n^{\log_b a})); if equal then (O(n^d \log n)); if (a < b^d) then (O(n^d)).

Recognition Cues

Phrases: "merge sorted", "sort array", "partition around pivot", "range minimum query", "count inversions", "closest pair", "majority element", "binary search in sorted / rotated".
Shapes: array halves processed independently; tree on intervals [left, right]; parallel recursion with combine step.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Loading diagram…

Mental Model

Divide shrinks problem size geometrically; conquer solves atoms; merge stitches sorted halves or aggregates segment answers. Binary search is degenerate D&C: only one subproblem contains the answer—total depth (O(\log n)). Segment tree stores an aggregate on each segment node; query walks (O(\log n)) nodes covering the query interval.

Generic Recipe

Merge sort: split mid, recurse left/right, merge two sorted runs with two pointers.
Quicksort: pick pivot, partition so smaller left / greater right, recurse on both sides (watch duplicate-heavy inputs—use random pivot or introsort in practice).
Binary search: maintain invariant on answer lying in [low, high]; halve using predicate ok(mid).
Segment tree: build node for [left, right] from children; query splits range into tree disjoint cover.
Always define base case size 0/1 and merge/pivot behavior on duplicates.

Complexity

Merge sort: (O(n \log n)) time, (O(n)) extra space for merged arrays (or in-place variants differ).
Quicksort: average (O(n \log n)), worst (O(n^2)) on bad pivots.
Binary search: (O(\log n)) predicate calls on finite search space.
Segment tree: build (O(n)), query/update (O(\log n)), space (O(n)).

Generic Code Template

Go

package main

func mergeSort(values []int) []int {
	length := len(values)
	if length <= 1 {
		out := make([]int, length)
		copy(out, values)
		return out
	}
	middle := length / 2
	left := mergeSort(values[:middle])
	right := mergeSort(values[middle:])
	return mergeRuns(left, right)
}

func mergeRuns(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	leftIndex, rightIndex := 0, 0
	for leftIndex < len(left) && rightIndex < len(right) {
		if left[leftIndex] <= right[rightIndex] {
			result = append(result, left[leftIndex])
			leftIndex++
		} else {
			result = append(result, right[rightIndex])
			rightIndex++
		}
	}
	result = append(result, left[leftIndex:]...)
	result = append(result, right[rightIndex:]...)
	return result
}

func partitionHoare(values []int, low, high int) int {
	pivot := values[low+(high-low)/2]
	left, right := low, high
	for {
		for values[left] < pivot {
			left++
		}
		for values[right] > pivot {
			right--
		}
		if left >= right {
			return right
		}
		values[left], values[right] = values[right], values[left]
		left++
		right--
	}
}

func binarySearchLowerBound(sorted []int, target int) int {
	low, high := 0, len(sorted)
	for low < high {
		middle := low + (high-low)/2
		if sorted[middle] < target {
			low = middle + 1
		} else {
			high = middle
		}
	}
	return low
}

func main() {}

JavaScript

function mergeSort(values) {
  if (values.length <= 1) {
    return [...values];
  }
  const middle = Math.floor(values.length / 2);
  const left = mergeSort(values.slice(0, middle));
  const right = mergeSort(values.slice(middle));
  return mergeRuns(left, right);
}

function mergeRuns(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex += 1;
    } else {
      result.push(right[rightIndex]);
      rightIndex += 1;
    }
  }
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

function partitionHoare(values, low, high) {
  const pivot = values[low + Math.floor((high - low) / 2)];
  let left = low;
  let right = high;
  while (true) {
    while (values[left] < pivot) {
      left += 1;
    }
    while (values[right] > pivot) {
      right -= 1;
    }
    if (left >= right) {
      return right;
    }
    [values[left], values[right]] = [values[right], values[left]];
    left += 1;
    right -= 1;
  }
}

function binarySearchLowerBound(sorted, target) {
  let low = 0;
  let high = sorted.length;
  while (low < high) {
    const middle = Math.floor(low + (high - low) / 2);
    if (sorted[middle] < target) {
      low = middle + 1;
    } else {
      high = middle;
    }
  }
  return low;
}

Variants

Merge sort — stable merges; also inversion counting with merge step augmentation.
Quicksort / quickselect — partition schemes (Lomuto, Hoare); Dutch flag for three-way partition on duplicates.
Binary search on answer — predicate monotonicity turns optimization into search (Binary search pattern).
Segment tree / Fenwick — range sums/min with point updates; recursive build over [left, right].

Representative Problems

704. Binary Search — two-pointer halving on sorted array
023. Merge K Sorted Lists — divide lists and merge pairs
004. Median of Two Sorted Arrays — partition / binary search on answer space

Anti-patterns

Quicksort always picking ends on sorted input—guarding with random pivot or median-of-three.
Merge sort merging in place naively with (O(n^2)) shifts—use temporary buffer or another algorithm.
Segment tree lazy propagation forgotten when range updates required—answers become stale.
Calling structure "D&C" when it is a single branch (binary search) without merge step—still recursive halving, but different analysis mindset.

On this page