Recursion in Divide & Conquer

Divide & conquer recursion splits input in half, solves recursively, and merges—cost is merge step plus 2*T(n/2) style recurrences.

Why this shows up in the real world

Merge sort, closest pair, and Karatsuba multiply follow this template.

Core idea (explained for students)

Prove merge is O(n); master theorem gives O(n log n) overall. Recursion depth O(log n) for balanced splits.

Try this in Python

def merge(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out: list[int] = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    return out + a[i:] + b[j:]


print(merge([1, 3], [2, 4]))

Common mistakes

• Uneven splits break balance → linear depth.
• Forgetting to copy subranges when mutating shared array.

Key takeaways

• Contrast with backtracking DFS which explores choices, not halves.
• Implement merge sort merge as standalone function for clarity.