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)).

Core Basics

Object: split problem, conquer pieces, merge with recurrence (T(n) = aT(n/b)+f(n)); includes merge-sort style combine.
Watchouts: merge step must stay (O(n)) when aiming for (O(n log n)); avoid hidden (O(n^2)) combines.
Staff-level bar: cite Master theorem verbally for asymptotics and sketch merge logic before coding.

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.

Use-case Lens

Best when: the input can be split into independent subproblems and combined cleanly.
Not for: subproblems that heavily overlap; use DP/memoization.
Main invariant: solve smaller instances of the same problem, then merge without losing information.
Interview move: write the recurrence (T(n) = aT(n/b) + f(n)) and explain combine cost.

Diagram

Loading diagram…

Step-by-step Visual

Example: Merge sort [5, 2, 4, 1]. Divide until each piece is easy, then combine sorted answers.

Loading diagram…

Understanding

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)).

Memory Hooks

Operational mantra: split into smaller independent ranges, solve them, then combine without losing cross-boundary answers.
Anti-panic: identify split, base case, and combine; if there is no combine, it may be binary search rather than full D&C.

Study Pattern (SDE3+)

Recognition drill (10 min): separate merge-based recursion, partition-based selection, interval recursion, and search-halving prompts.
Implementation sprint (25 min): code merge sort merge logic and quickselect partition; state expected vs worst-case time.
Staff follow-up (10 min): discuss recursion depth, stable merging, randomized pivots, and parallelizable subproblems.

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