Pattern Guide
Divide and Conquer
"Split. Solve each half. Merge. Repeat until trivial."
Divide and conquer splits a problem into independent subproblems, solves each recursively, and merges results. Merge sort, quick sort, closest pair of points, count inversions, and maximum subarray all follow this pattern. The merge step is where the real work happens.
18 min readgraph problems →
Problems you can solve with this pattern
5 problems · click any to start solving
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);
}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);
}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)
- "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)