All patterns
Divide and Conquer
Split, solve halves independently, combine.
time O(n log n) for the classic 2-way splitspace O(n) plus O(log n) stack
What it is
Break the problem into independent subproblems of the same kind, solve them recursively and merge results. The Master theorem gives the cost: T(n) = a·T(n/b) + f(n).
When to reach for it
- Sorting
- Counting inversions
- Closest pair, maximum crossing subarray
- Tree-shaped recursion with balanced halves
Clues in the problem
- Two recursive calls on n/2
- A linear merge step
Template
def merge_sort(a):if len(a) <= 1:return amid = len(a) // 2l, r = merge_sort(a[:mid]), merge_sort(a[mid:])out, i, j = [], 0, 0while i < len(l) and j < len(r):if l[i] <= r[j]:out.append(l[i]); i += 1else:out.append(r[j]); j += 1return out + l[i:] + r[j:]
Practice problems
- Merge Sort
- Count of Smaller Numbers After Self
- Kth Largest (quickselect)
- Maximum Subarray (D&C form)
Common mistakes
- Slicing copies that hide extra O(n) per level
- Unbalanced splits degrading to O(n²)
- Missing base case