Split the problem, solve the pieces, combine the answers. It is the paradigm behind merge sort, quick sort and binary search — and the recursion tree shows exactly where the log n comes from.
Controls
array size n8
The Recursion Tree
step 0
Insight
Three phases at every level: divide into subproblems, conquer them recursively, combine the results.
T(n) = a·T(n/b) + f(n)
↑ ↑ ↑
pieces size combine
levels0
work / level0
total0
Complexity
Merge sortO(n log n)
Binary searchO(log n)
DepthO(log n)
Overview
Divide and conquer splits a problem into smaller instances, solves them, and combines their results. It works when subproblems are easier to solve and their answers can be combined efficiently, as in merge sort.
The problem it solves
The canonical example is merge sort. It divides the array in half, recursively sorts each half, and merges the two sorted halves. The merge step does O(n) work, and there are O(log n) levels of recursion.
Where log n Comes From
The recursion tree makes it obvious. Each level halves the problem size, so it takes log₂n levels to reach size 1 — that is the height of the tree.
In merge sort, every level does O(n) total work (each element is touched once during merging), and there are log n levels. Multiply: O(n log n). Raise n in the lab and watch the level count grow by exactly one each time you double.
The Master Theorem
For recurrences of the form T(n) = a·T(n/b) + f(n) — a subproblems of size n/b, plus f(n) to combine — the answer depends on which dominates:
Leaves dominate — most work at the bottom.
Balanced — equal work per level, giving the extra log factor. Merge sort sits here: T(n) = 2T(n/2) + O(n) → O(n log n).
Root dominates — the combine step is the expensive part.
Binary search is T(n) = T(n/2) + O(1): one subproblem, trivial combine. So O(log n) total. It discards half the work rather than recursing into both halves. This is why it beats merge sort's cost.
The Combine Step Is Where the Work Lives
Dividing is usually trivial — compute a midpoint. The interesting engineering is almost always in combining.
Merge sort — merging two sorted halves is O(n) and needs O(n) scratch space.
Quick sort — inverts the pattern: it partitions before recursing. So the combine step is free. That is why it sorts in place.
Maximum subarray — the answer may straddle the midpoint, so combining must scan outward from the centre.
Why It Matters Beyond Sorting
Divide and conquer parallelises naturally — free subproblems can run on different cores. This is why it underpins MapReduce and most parallel frameworks. It is also the pattern behind Karatsuba multiplication, the Fast Fourier Transform, and closest-pair-of-points.
Split, solve, combine
Divide and conquer solves a problem by breaking it into free subproblems of the same kind, solving those recursively, and combining the results.
Three steps, and the third is where the algorithms differ:
Divide the problem into smaller instances. Conquer each recursively, until a base case is trivial. Combine the sub-results into the answer.
Algorithm
Divide
Combine
Merge sort
Split in half
Merge two sorted halves — O(n)
Quick sort
Partition around a pivot
Nothing — work done in the divide
Binary search
Halve the range
Nothing — one side is discarded
Karatsuba multiplication
Split the digits
Three products and some additions
Strassen's matrix product
Split into quadrants
Seven products and additions
Closest pair of points
Split by x-coordinate
Check the strip near the boundary
Note that quick sort and merge sort are mirror images: quick sort does its work partitioning before recursing, merge sort does it merging afterwards. Binary search is the degenerate case where one subproblem is discarded fully. This is why it is O(log n) rather than O(n log n).
Experiments to try with Divide and Conquer
Step through merge sort at n = 8. Watch the tree split down to single elements. Then merge back upward.
Count the levels: 3 for n = 8. That is log₂8. And it is exactly where the log n factor comes from.
Common mistakes with Divide and Conquer
Using it where subproblems overlap. That is dynamic programming, and without caching the cost is exponential.
Forgetting the base case, giving infinite recursion.
An expensive combine step that dominates and negates the saving.
Recursion depth on large inputs in Python — convert to iteration or raise the limit.
Ignoring the constant factor. Recursion has overhead; below a threshold a simple loop wins. This is why real sorts switch to insertion sort for small subarrays.
Copying data at every level.arr[:mid] allocates; passing indices into one array avoids it.
Two problems that look nothing alike solved by the same shape: fast exponentiation, which turns 1,000 multiplications into 10, and counting inversions during a merge, which does in n log n what the obvious loop does in n².
divide_and_conquer.pyPython 3
# Divide and conquer: split, solve the pieces, combine.
# --- 1. exponentiation by squaring -------------------------------------
def power(base, exp, depth=0):
pad = " " * depth
if exp == 0:
return 1
half = power(base, exp // 2, depth + 1) # ONE recursive call, not two
result = half * half
if exp % 2:
result *= base # odd: one extra factor
print(f"{pad}power({base}, {exp}) = {result}")
return result
print("2 ** 10 by squaring:")
print("result:", power(2, 10))
print("multiplications: about log2(10) = 4, not 10")
# --- 2. counting inversions while merge sorting ------------------------
def sort_and_count(a):
if len(a) <= 1:
return a, 0
mid = len(a) // 2
left, x = sort_and_count(a[:mid])
right, y = sort_and_count(a[mid:])
merged, z = [], 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
# left[i:] are ALL bigger than right[j], so they are all inversions
z += len(left) - i
merged.append(right[j]); j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, x + y + z
def count_brute(a):
return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])
data = [2, 4, 1, 3, 5, 8, 7, 6]
sorted_data, inversions = sort_and_count(data)
print()
print("list :", data)
print("sorted :", sorted_data)
print("inversions :", inversions, "(brute force agrees:", count_brute(data), ")")
print()
print("Brute force compares every pair: O(n^2).")
print("The merge counts them in blocks while it is sorting anyway: O(n log n).")
Output
How the code works
half = power(base, exp // 2, depth + 1)One recursive call, and its result is used twice. Writing power(b, n//2) * power(b, n//2) instead looks identical and is exponentially slower — the saving is in reusing the value, not in the halving.
if exp % 2: result *= baseHandles the odd case, where halving loses a factor. This is where off-by-one errors live in every implementation of this function.
left, x = sort_and_count(a[:mid])The divide step. Each half is solved independently, and the returned count is the number of inversions within that half.
z += len(left) - iThe combine step, and the clever line. When an item from the right half wins, every remaining item on the left is greater than it, so they are all inversions — counted in one addition instead of one by one.
x + y + zLeft, right, and across. Every inversion is in exactly one of those three categories, which is the proof that the count is complete. That decomposition is the divide-and-conquer pattern in general.
Change one thing
Compute power(2, 1000). Ten recursive calls, and Python's unbounded integers print the whole 302-digit result.
Run the inversion counter on a reversed list of 12 items. The answer is n(n−1)/2, the maximum possible — and it is the same number insertion sort would charge you in shifts.
Time both counters on a list of 2,000 random numbers. The brute force does two million comparisons; the merge does about twenty thousand.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Predict, then reveal
About to run: Step through merge sort at n = 8. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
Why does exponentiation by squaring make ONE recursive call and reuse the result?
power(b, n//2) * power(b, n//2) looks identical and is exponentially slower. The saving is in reusing the value, not in the halving.
Counting inversions during a merge is O(n log n) because, when an item from the right half wins:
The left half is sorted, so all of its remainder is greater. Counting in blocks rather than pairs is the whole trick.
Divide and conquer proves its answer complete by showing every case falls into:
Every inversion is within one half or spans both, and never anything else. That decomposition is the pattern in general, not just here.
Cheat sheet
Divide and Conquer
Split a problem in half, recurse, combine — and see how halving at each level gives merge sort its O(n log n) guarantee.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.