Divide & Conquer

"Master theorem, merge sort, quick sort, closest pair, maximum subarray (D&C)."

Deep Dive Tutorial

Divide and conquer has three steps: divide the problem into smaller subproblems, conquer each recursively (base case when trivial), and combine the results. The key insight is that combining partial results is cheaper than solving the full problem directly. Merge sort is the canonical example: splitting is O(1), merging is O(n), recursion depth is O(log n), total O(n log n).

Problem	Split	Merge cost	Total
Merge Sort	Half/half	O(n) merge two sorted halves	O(n log n)
Quick Sort	Partition around pivot	O(n) partition	O(n log n) avg
Count Inversions	Half/half	O(n) count cross-half inversions during merge	O(n log n)
Closest Pair of Points	Half/half by x	O(n) strip check	O(n log n)
Maximum Subarray	Half/half	O(n) find max crossing subarray	O(n log n)
QuickSelect (k-th smallest)	Partition	O(1) — only recurse one side	O(n) avg

Merge Sort Template

Merge sort — the canonical D&C example

function mergeSort(arr) {
    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(left, right) {
    const result = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length)
        result.push(left[i] <= right[j] ? left[i++] : right[j++]);
    return result.concat(left.slice(i), right.slice(j));
}

// In-place merge sort with index tracking (avoids array slices)
function mergeSortInPlace(arr, lo, hi, temp) {
    if (lo >= hi) return;
    const mid = (lo + hi) >> 1;
    mergeSortInPlace(arr, lo, mid, temp);
    mergeSortInPlace(arr, mid+1, hi, temp);
    mergeInPlace(arr, lo, mid, hi, temp);
}

QuickSelect — O(n) Average k-th Element

QuickSelect — find k-th smallest in O(n) average

function quickSelect(arr, lo, hi, k) {
    if (lo === hi) return arr[lo];
    const pivot = partition(arr, lo, hi);
    if (k === pivot) return arr[pivot];
    if (k < pivot) return quickSelect(arr, lo, pivot - 1, k);
    return quickSelect(arr, pivot + 1, hi, k);
}

function partition(arr, lo, hi) {
    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++]];
    }
    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
}

// Usage: k-th smallest (0-indexed)
// quickSelect(arr, 0, arr.length-1, k-1)

// Randomized pivot for O(n) expected (not worst case O(n²)):
function randPartition(arr, lo, hi) {
    const r = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[r], arr[hi]] = [arr[hi], arr[r]];
    return partition(arr, lo, hi);
}

Worked Problems

Sort an Array (Merge Sort)

Medium

Solve ↗

Kth Largest Element in an Array

Medium

Solve ↗

Count of Smaller Numbers After Self

Hard

Solve ↗

Maximum Subarray (Divide & Conquer)

Medium

Solve ↗

Reverse Pairs

Hard

Solve ↗

brain

D&C pattern recognition:
- "Sort / order statistics" → merge sort or quick sort
- "K-th smallest/largest" → QuickSelect O(n) avg
- "Count inversions / cross-half pairs" → merge sort, count during merge
- "Max subarray crossing midpoint" → D&C merge step
- "Closest pair of points" → sort by x, split, check strip O(n log² n)

When D&C beats DP:
- Independent subproblems (no shared state between halves)
- The merge step does useful work (counts/computes something nontrivial)
- Naturally recursive structure (trees, sorted arrays)

← All Patterns