Released · improving
Algorithm
Divide and conquer splits a problem into smaller subproblems, solves them recursively and combines the results, as in merge sort and fast exponentiation.
Divide and conquer is an algorithm design technique: split a problem into smaller instances of the same problem (divide), solve them recursively (conquer), and build the final answer from their results (combine). Merge sort, binary search, fast exponentiation, quickselect, Karatsuba multiplication and the closest-pair algorithm all follow this pattern.
It matters because it often turns an O(n^2) brute-force solution into O(n log n) or even O(log n). The key trick of computing information that crosses the split during the combine step, as in counting inversions, comes up again and again in coding interviews, and the same ideas power sorting libraries, big-number multiplication, the FFT and modular exponentiation in cryptography.
Start by tracing merge sort by hand to internalize divide, conquer and combine, then practice writing recurrences such as T(n) = aT(n/b) + f(n) and solving them with the master theorem. Next, implement counting inversions, fast power and quickselect yourself, and learn to tell when overlapping subproblems call for dynamic programming instead.
Divide the input, solve the parts recursively and combine the answers. A base case stops the recursion, and the combine cost usually decides the running time.
Write the running time as T(n) = aT(n/b) + f(n) and compare f(n) with n^(log_b a) to read off results such as O(n log n) for merge sort.
Handling the cases that straddle both halves in linear time, as in counting inversions or the maximum subarray, is the central idea.
Keeping only one subproblem, as binary search, fast power and quickselect do, gives O(log n) or expected O(n) algorithms.
sort_count sorts the list with merge sort and, whenever an element from the right half is merged first, adds the number of elements still waiting on the left, which counts inversions in O(n log n). power is fast exponentiation: it halves the exponent and squares, so it needs only O(log e) multiplications. Running python divide_and_conquer.py prints the sorted list with its 14 inversions and 3^200 modulo 1,000,000,007.
divide_and_conquer.py
def sort_count(a):
"""Return (sorted list, number of inversions) using merge sort."""
if len(a) <= 1:
return list(a), 0
mid = len(a) // 2
left, x = sort_count(a[:mid])
right, y = sort_count(a[mid:])
merged, i, j, cross = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
cross += len(left) - i # right[j] is smaller than every left[i:]
merged += left[i:] + right[j:]
return merged, x + y + cross
def power(base, exp, mod):
"""base ** exp % mod with O(log exp) multiplications."""
if exp == 0:
return 1 % mod
half = power(base, exp // 2, mod)
result = half * half % mod
return result * base % mod if exp % 2 else result
if __name__ == "__main__":
print(sort_count([5, 2, 4, 7, 1, 3, 2, 6])) # ([1, 2, 2, 3, 4, 5, 6, 7], 14)
print(power(3, 200, 1_000_000_007)) # 136318165
python divide_and_conquer.pySix chapters that take you from installation to the core ideas of Divide and conquer.
Ask questions, share experience and trade opinions about Divide and conquer.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.