ZERO / HERO
Split the pile, solve, combine

Divide & Conquer

The analogy

Break the problem into independent halves, solve each the same way, then stitch the answers together. The interesting part is always the stitching — that is where the real work and the real insight live.

Visualizer

Split, solve, combine

step 1 / 10
5
3
8
1
9
2
7
4

Count inversions in [5, 3, 8, 1, 9, 2, 7, 4] — pairs that are out of order. The naive way compares every pair: O(n²).

def count_inversions(a):
    if len(a) < 2:
        return a, 0
    mid = len(a) // 2
    left,  x = count_inversions(a[:mid])
    right, y = count_inversions(a[mid:])
    merged, cross = [], 0
    i = j = 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      # the insight
    merged += left[i:] + right[j:]
    return merged, x + y + cross

# Master Theorem: T(n) = a T(n/b) + f(n)
#   2 T(n/2) + O(n)   -> O(n log n)   merge sort
#   3 T(n/2) + O(n)   -> O(n^1.585)   Karatsuba
Check yourself

Recursive subproblems overlap heavily. What does that indicate?