Divide and conquer
In one line
Split the problem into independent smaller parts, solve each part recursively, then combine the answers, which often turns an O(n^2) approach into O(n log n).
What it is
Divide and conquer has three steps. Divide: split the input into smaller parts, usually halves. Conquer: solve each part recursively, with tiny inputs as the base case. Combine: merge the partial answers into the answer for the whole input.
The parts must be independent, meaning each can be solved without knowing the others' answers. That is what separates it from dynamic programming, where subproblems overlap. Classic examples are merge sort, quicksort, binary search (which only needs to conquer one half), counting inversions, Karatsuba multiplication and the closest pair of points.
Why interviewers ask
It is how many of the fastest known algorithms work, and interviewers use it to test recursive thinking and complexity analysis together. The hard part is usually the combine step: for counting inversions or the maximum subarray crossing the middle, a clever O(n) combine is what makes the whole algorithm O(n log n).
How it works
- 1Choose how to split: by position (halves of an array), by value (quicksort's pivot), or by space (left and right halves of a set of points).
- 2Define the base case: usually a size 0 or 1 input whose answer is obvious.
- 3Recursively solve each part. Trust that the calls return correct answers for their halves.
- 4Combine: the step that does real work. Merge sort merges two sorted lists in O(n); inversion counting also counts pairs that cross the split while merging.
- 5Analyse with the recurrence. Two halves plus O(n) combine is T(n) = 2T(n/2) + O(n) = O(n log n).
Worked example · Merge sort with inversion counting on [5, 2, 4, 1]
- Divide [5, 2, 4, 1] into [5, 2] and [4, 1].
- [5, 2] splits into [5] and [2]. Merge: 2 < 5, so take 2 first. Since 2 jumped ahead of 1 remaining left item, that is 1 inversion. Result [2, 5].
- [4, 1] splits into [4] and [1]. Merge gives [1, 4] with 1 inversion.
- Merge [2, 5] and [1, 4]. Compare 2 and 1: take 1, it jumps ahead of 2 left items (2 and 5), so +2. Compare 2 and 4: take 2. Compare 5 and 4: take 4, it jumps ahead of 1 left item (5), so +1. Then take 5. Result [1, 2, 4, 5] with 3 crossing inversions.
- Total inversions = 1 + 1 + 3 = 5. Check by hand: (5,2), (5,4), (5,1), (2,1), (4,1). Five pairs, found in O(n log n) instead of checking all O(n^2) pairs.
Picture it
Sorting a huge pile of exam papers by name is easier if you split the pile between two helpers, who each split theirs again, until everyone has one or two papers. Then pairs of people merge their sorted piles, those merge again, and so on, until one fully sorted pile comes back to you.
Reference code
def sort_and_count(a):
# returns (sorted copy of a, number of inversions i < j with a[i] > a[j])
if len(a) <= 1:
return a, 0
mid = len(a) // 2
left, inv_left = sort_and_count(a[:mid]) # divide + conquer
right, inv_right = sort_and_count(a[mid:])
merged, i, j, inv = [], 0, 0, inv_left + inv_right
while i < len(left) and j < len(right): # combine
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
inv += len(left) - i # right[j] is smaller than all remaining left items
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, inv
print(sort_and_count([5, 2, 4, 1])) # ([1, 2, 4, 5], 5)
The divide step splits at mid, the conquer step recurses on both halves, and the combine step merges them. When right[j] is placed before the remaining len(left) - i items of the left half, each of those forms an inversion with it, so the count comes for free during the merge.
Key patterns
Split in half, merge
When: Sorting, counting inversions, merging k sorted lists pairwise
How: Recurse on halves, combine with a linear merge. O(n log n).
Partition around a pivot
When: Quicksort, quickselect for the k-th smallest
How: Put smaller items left and larger right, then recurse on one or both sides. Average O(n log n) for sort and O(n) for select; worst case O(n^2) without good pivots.
Decrease and conquer
When: Binary search, fast power
How: Only one part needs solving, so T(n) = T(n/2) + O(1) = O(log n).
Answer crosses the middle
When: Maximum subarray, closest pair of points
How: Best answer is in the left half, the right half, or crosses the split; compute the crossing case in O(n) during combine.
Real-world use
Library sorting routines
Java's Arrays.sort for objects and Python's sorted use Timsort, a merge-based sort; Java's Arrays.parallelSort splits the array across threads with the Fork/Join framework and merges the sorted pieces.
MapReduce and Spark
Hadoop MapReduce and Apache Spark split a huge dataset into partitions processed on different machines, then combine partial results, such as summing word counts per word, in a reduce step.
C++ std::sort
Common implementations such as libstdc++ use introsort: quicksort's partition-and-recurse, switching to heapsort if recursion gets too deep, which guarantees O(n log n) in the worst case.
git bisect
git bisect finds the commit that introduced a bug by testing the middle commit and discarding half the history each time, so 1,000 commits need only about 10 tests.
In a project
A music streaming app wants a 'taste similarity' score between two users: given both users' rankings of the same 100,000 songs, count how many song pairs they order differently.
- Map each song to its position in user A's ranking, then rewrite user B's ranking as the sequence of user A's positions.
- The number of pairs ordered differently is the number of inversions in that sequence.
- Count inversions with merge sort, adding len(left) - i each time an item from the right half is taken before remaining left items.
- Normalise by n(n - 1)/2 to get a 0 to 1 distance (this is Kendall tau distance).
Impact: The brute-force pair check needs about 5 billion comparisons for 100,000 songs; divide and conquer needs about 1.7 million steps (n log2 n), turning minutes into milliseconds, so similarity can be computed on demand for recommendations.
Trade-offs
Use it when
- The problem splits into independent parts of similar size
- A fast combine step exists (linear or better)
- Work can be parallelised across cores or machines
Avoid it when
- Subproblems overlap and repeat; use memoization or DP instead
- Splits are very unbalanced, like quicksort with a bad pivot on sorted input, which degrades to O(n^2)
- Input is tiny; a simple O(n^2) method like insertion sort is faster below about 16 to 32 items, which is why Timsort and introsort use it for small runs
Cost: Merge sort O(n log n) time, O(n) extra space. Quicksort O(n log n) average, O(n^2) worst, O(log n) average stack. Binary search O(log n). Karatsuba O(n^1.585).
Common mistakes
- Confusing divide and conquer with DP: DP is for overlapping subproblems, divide and conquer for independent ones.
- Making the combine step O(n^2), which loses the whole speed-up.
- Slicing arrays at every level in performance-critical code without counting the extra copies; pass indices instead where it matters.
- Forgetting the crossing case, such as subarrays that span the midpoint.
- Claiming quicksort is always O(n log n); the worst case is O(n^2).
Interview questions
Quick revision
- Divide, conquer recursively, combine.
- Subproblems are independent (unlike DP).
- 2T(n/2) + O(n) = O(n log n).
- Inversions: count len(left) - i during merge.
- Quicksort: average O(n log n), worst O(n^2).
- Quickselect: average O(n).
- Look for the answer that crosses the middle.
Check yourself
1. What distinguishes divide and conquer from dynamic programming?
2. How many inversions does [3, 1, 2] have?
3. What is the worst-case time of quicksort with a pivot that is always the smallest element?
4. Why does merge sort take O(n log n)?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.