Divide and Conquer: Fast Power and Merge Sort
24 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Some problems split cleanly in half. Solve each half the same way, then combine the answers. This lesson covers that idea with two classics, fast power and merge sort, and shows why halving keeps recursion shallow and fast.
Split, solve, combine
Divide and conquer is a method that splits a problem into smaller parts of the same kind, solves each part recursively, and combines the answers. The parts are usually halves, so the depth is about log n.
To find the largest order among thousands, split the list in two, find the largest of each half, and compare. Each half is the same problem, only smaller.
def largest(items, low, high): if low == high: return items[low] middle = (low + high) // 2 left = largest(items, low, middle) right = largest(items, middle + 1, high) return max(left, right)
print(largest([40, 95, 15, 60, 72], 0, 4))Halving 1000 items takes only 10 levels, so the stack stays small. A plain loop is still simpler here. Use this shape when the combine step does real work.
Fast power
Fast exponentiation computes base to the power n by squaring: it finds the power for n // 2, squares it, and multiplies by base once more when n is odd. It needs only O(log n) multiplications.
A loop that multiplies n times is slow for huge n. Squaring a half result does the same job: x to the 30th is the square of x to the 15th.
def power(base, n): if n == 0: return 1 half = power(base, n // 2) if n % 2 == 0: return half * half return half * half * base
print(power(2, 30), power(3, 13))Example 1 · Slow against fast power
def slow_power(base, n): result = 1 for _ in range(n): result *= base return result
steps = 0
def power(base, n): global steps steps += 1 if n == 0: return 1 half = power(base, n // 2) return half * half if n % 2 == 0 else half * half * base
print(slow_power(3, 1000) == power(3, 1000))print(steps, "calls instead of 1000 multiplications")True 11 calls instead of 1000 multiplications
What this code does
- The loop does 1000 multiplications. The recursive version makes 11 calls.
- Both give the same exact integer, since Python integers never overflow.
Example 2 · Power with a remainder
def power_mod(base, n, m): if n == 0: return 1 % m half = power_mod(base, n // 2, m) result = half * half % m return result * base % m if n % 2 else result
print(power_mod(7, 128, 13))print(pow(7, 128, 13))3 3
What this code does
- Taking the remainder at every step keeps numbers small, which matters for huge exponents.
- The built-in
pow(base, n, m)does the same job in one call.
The exponent halves each call, so only O(log n) calls happen. Call power once and reuse half. Calling it twice would bring the cost back to O(n).
Merging two sorted lists
Merge step combines two sorted lists into one sorted list by repeatedly taking the smaller of the two front items. It makes one pass and takes O(n) time.
Two lists of marks are already sorted. Walk both with one pointer each and always take the smaller front item.
def merge(left, right): result, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 return result + left[i:] + right[j:]
print(merge([20, 50, 90], [30, 40]))Example 3 · Merge marks
def merge(left, right): result, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 return result + left[i:] + right[j:]
print(merge([20, 50, 90], [30, 40, 95, 99]))[20, 30, 40, 50, 90, 95, 99]
What this code does
- The loop stops when one list runs out.
- The slices at the end copy the leftover items of the other list.
Each item is moved once, so merging n items takes O(n) time. The two leftover slices at the end add whatever remains of the longer list.
Merge sort
Merge sort is a divide-and-conquer sort that splits a list in half, sorts both halves recursively and merges them. It takes O(n log n) time in every case and O(n) extra space.
Split the list in half, sort each half by the same method, and merge the two sorted results. A list of one item is already sorted.
from heapq import merge
def merge_sort(items): if len(items) <= 1: return items middle = len(items) // 2 left = merge_sort(items[:middle]) right = merge_sort(items[middle:]) return list(merge(left, right))
print(merge_sort([5, 2, 9, 1, 7]))Example 4 · Merge sort by hand
def merge(left, right): result, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 return result + left[i:] + right[j:]
def merge_sort(items): if len(items) <= 1: return items middle = len(items) // 2 return merge(merge_sort(items[:middle]), merge_sort(items[middle:]))
marks = [64, 91, 18, 77, 45, 18, 90]print(merge_sort(marks))print(merge_sort(marks) == sorted(marks))[18, 18, 45, 64, 77, 90, 91] True
What this code does
- Equal marks stay in arrival order because the merge takes from the left on ties (
<=). - The result matches the built-in
sorted.
heapq.merge is the library version of the merge step. In an interview, write the merge step by hand as in the example below.
What divide and conquer costs
Merge sort splits log n times, and each level merges n items in total. Python's own sort is faster in practice, but this shows where n log n comes from.
Example 5 · Depth and comparisons
import random
compares = 0deepest = 0
def merge(left, right): global compares result, i, j = [], 0, 0 while i < len(left) and j < len(right): compares += 1 if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 return result + left[i:] + right[j:]
def merge_sort(items, depth=1): global deepest deepest = max(deepest, depth) if len(items) <= 1: return items middle = len(items) // 2 return merge(merge_sort(items[:middle], depth + 1), merge_sort(items[middle:], depth + 1))
random.seed(7)data = random.sample(range(10_000), 1000)merge_sort(data)print(deepest, "levels")print(compares < 10_000, "comparisons are below 10,000")print(1000 * 999 // 2, "pairs a slow sort may compare")11 levels True comparisons are below 10,000 499500 pairs a slow sort may compare
What this code does
- 1000 items need about 11 levels, not 1000, so the stack is tiny.
- Merge sort compares under 10,000 times, while comparing every pair would need 499,500.
Next step
Check your understanding
11 quick questions