Divide and Conquer

Overview

Divide and conquer splits a problem into smaller, independent subproblems, solves each recursively, and merges their solutions. It underpins classic algorithms like merge sort, quicksort, and fast exponentiation. When the subproblems are balanced, the running time follows the Master Theorem; merge sort, for example, is O(n log n) time.

Syntax / Usage

The recipe has three steps: divide the input, conquer each half recursively, and combine. The base case handles inputs small enough to solve directly.

def merge_sort(nums):                 # O(n log n) time, O(n) space
    if len(nums) <= 1:                # base case: already sorted
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])     # conquer left half
    right = merge_sort(nums[mid:])    # conquer right half
    return merge(left, right)         # combine sorted halves

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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Examples

Sort a list with merge sort:

print(merge_sort([5, 2, 9, 1, 5, 6]))  # [1, 2, 5, 5, 6, 9]

Fast exponentiation halves the exponent each step for O(log n) multiplications:

def power(base, exp):                 # O(log exp) time
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    return half * half * (base if exp % 2 else 1)

print(power(2, 10))  # 1024

Common Mistakes

• Forgetting the base case, so recursion never terminates.
• Splitting into subproblems that overlap; that calls for dynamic programming, not pure divide and conquer.
• Doing expensive work in the combine step and underestimating its cost in the recurrence.
• Slicing lists in Python repeatedly, which adds hidden O(n) copies per level.
• Assuming balanced splits; a skewed split (like bad quicksort pivots) degrades to O(n^2).

See Also

algorithms-recursion algorithms-sorting algorithms-binary-search-patterns