Learn how divide and conquer splits a problem into smaller subproblems, solves them recursively, and combines the results.

Divide and Conquer

Divide and conquer is a recursive strategy that solves a problem by splitting it into smaller subproblems of the same type, solving each subproblem recursively, and combining the results. It is the engine behind merge sort, binary search, quicksort, and many other fundamental algorithms.

Three steps every time:

Divide — split the problem into smaller subproblems
Conquer — solve each subproblem recursively (base case when small enough to solve directly)
Combine — merge the solutions to produce the final answer

Divide and Conquermerge sort · O(n log n)

Array state

[0]

[1]

[2]

[3]

[4]

[5]

[6]

dividing

merging

merged

waiting

merge_sort.py

def merge_sort(arr, lo, hi):

if lo >= hi: return # base case

mid = (lo + hi) // 2 # divide

merge(arr, lo, mid, hi) # combine

# subarray now sorted

return arr

Start merge sort — divide [38, 27, 43, 3, 9, 82, 10] into halves

step 0/26

Example — maximum subarray sum (Kadane's recursive version)

Given an array, find the contiguous subarray with the largest sum.

def max_subarray(arr, lo, hi):
    # base case — single element
    if lo == hi:
        return arr[lo]

    mid = (lo + hi) // 2

    # conquer left and right halves
    left_max = max_subarray(arr, lo, mid)
    right_max = max_subarray(arr, mid + 1, hi)

    # combine — the answer might span the midpoint
    # find max crossing subarray
    left_sum = float("-inf")
    total = 0
    for i in range(mid, lo - 1, -1):
        total += arr[i]
        left_sum = max(left_sum, total)

    right_sum = float("-inf")
    total = 0
    for i in range(mid + 1, hi + 1):
        total += arr[i]
        right_sum = max(right_sum, total)

    cross_max = left_sum + right_sum

    return max(left_max, right_max, cross_max)


arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(arr, 0, len(arr) - 1))   # 6 → [4,-1,2,1]

Example — binary search (divide and conquer)

Binary search is divide and conquer — divide the array in half, conquer the relevant half, no combining step needed:

def binary_search(arr, target, lo, hi):
    if lo > hi:
        return -1   # base case — not found

    mid = (lo + hi) // 2

    if arr[mid] == target:
        return mid  # base case — found

    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # conquer right

    return binary_search(arr, target, lo, mid - 1)       # conquer left

Example — merge sort (divide, conquer, then merge)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr      # base case

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # conquer left
    right = merge_sort(arr[mid:])   # conquer right
    return merge(left, right)       # combine

Why divide and conquer is often O(n log n)

The Master Theorem gives a formula for divide and conquer recurrences of the form:

T(n) = a × T(n/b) + f(n)

where:
  a = number of subproblems
  b = factor by which input shrinks
  f(n) = cost of divide and combine steps

For merge sort: T(n) = 2 × T(n/2) + O(n) → O(n log n) For binary search: T(n) = 1 × T(n/2) + O(1) → O(log n) For naive matrix multiply: T(n) = 8 × T(n/2) + O(n²) → O(n³)

The key insight — if you can split a problem in half and the combine step is cheap (O(n) or less), you almost always get O(n log n). This is why divide and conquer is so powerful for sorting, searching, and many other problems that naively require O(n²).

Strassen's matrix multiplication

A famous application — naive matrix multiplication is O(n³) because it makes 8 recursive subproblems. Strassen noticed you can do it in 7 multiplications using clever algebra:

T(n) = 8 × T(n/2) + O(n²) → O(n³)   ← naive
T(n) = 7 × T(n/2) + O(n²) → O(n^2.81)  ← Strassen

Saving one multiplication per level of recursion changes the exponent from 3 to 2.81 — a significant speedup for very large matrices.

Divide and conquer vs dynamic programming

Both break problems into subproblems — the key difference is overlap:

	Divide and Conquer	Dynamic Programming
Subproblem overlap	No — each subproblem is unique	Yes — subproblems repeat
Recomputation	Not needed (no overlap)	Avoids with memoization
Examples	Merge sort, binary search	Fibonacci, knapsack

Fibonacci computed recursively is NOT divide and conquer — fibonacci(n-1) and fibonacci(n-2) both call fibonacci(n-3), so subproblems overlap. Dynamic programming handles this with caching. Merge sort IS divide and conquer — the left half and right half never share elements.

Complexity

Algorithm	Recurrence	Result
Binary search	T(n) = T(n/2) + O(1)	O(log n)
Merge sort	T(n) = 2T(n/2) + O(n)	O(n log n)
Quick sort (avg)	T(n) = 2T(n/2) + O(n)	O(n log n)
Naive matrix mult	T(n) = 8T(n/2) + O(n²)	O(n³)
Strassen	T(n) = 7T(n/2) + O(n²)	O(n^2.81)

Divide and Conquer

On this page