The Divide & Conquer Paradigm — Algorithms Course

What you'll learn

Divide and conquer is the first true design paradigm. You've already used it in merge sort, quick sort, and binary search — now we name the pattern, learn its analysis, and apply it to a fresh problem.

By the end you'll be able to:

Describe the three steps: divide, conquer, combine
Recognize the template in code
Analyze a D&C algorithm with a recurrence
Apply it to counting inversions

Divide, conquer, combine

Every divide-and-conquer algorithm has the same skeleton:

The three steps of divide & conquer

Divide

Break the problem into smaller subproblems of the same kind.

Conquer

Solve each subproblem recursively (base case solves directly).

Combine

Merge the sub-answers into the answer for the whole problem.

Merge sort is the canonical example: divide the array in half, conquer by sorting each half, combine with a merge. The animation is worth a second look through this lens:

Divide & conquer in merge sort

Merge sort

1/5Merge sort: treat each element as a sorted run of size 1, then merge adjacent runs, doubling the run size each pass.

Splitting is the divide; merging sorted runs is the combine.

The template

Strip away the specifics and every D&C algorithm looks like this:

Language

divide_and_conquer.py

def divide_and_conquer(problem):
    if is_small(problem):                 # base case
        return solve_directly(problem)
    parts = divide(problem)               # divide
    results = [divide_and_conquer(p) for p in parts]   # conquer
    return combine(results)               # combine

Analyzing it

Because a D&C algorithm calls itself on smaller inputs, its cost is a recurrence T(n) = a·T(n/b) + O(nᵈ) — solved instantly by the Master Theorem from Module 3. Merge sort's T(n) = 2T(n/2) + O(n) gives O(n log n); binary search's T(n) = T(n/2) + O(1) gives O(log n).

Key idea

D&C pays off when the subproblems are substantially smaller and the combine step is cheap relative to the whole. If combining costs as much as solving from scratch, you gain nothing.

Counting inversions

How "out of order" is a list? An inversion is a pair i < j with a[i] > a[j]. Brute force checks all pairs in O(n²). But we can piggyback on merge sort: while merging, every time we take an element from the right half before the left is exhausted, it forms an inversion with every remaining left element — count them for free, in O(n log n):

Language

count_inversions.py

def count_inversions(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, x  = count_inversions(a[:mid])
    right, y = count_inversions(a[mid:])
    merged, z = merge_count(left, right)
    return merged, x + y + z            # inversions add up

def merge_count(l, r):
    out, i, j, inv = [], 0, 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            out.append(l[i]); i += 1
        else:
            out.append(r[j]); j += 1
            inv += len(l) - i           # l[i:] are all > r[j]
    return out + l[i:] + r[j:], inv

Tip

This is a recurring trick: take a problem that looks O(n²) and see whether the work can ride along inside a sort or a single D&C pass. Inversions, closest pair, and many geometry problems all yield to it.

Recap & quick check

Key takeaways

Divide & conquer = divide into subproblems, conquer recursively, combine the results.
Merge sort, quick sort, and binary search are all instances of it.
Its cost is a recurrence solved by the Master Theorem.
It pays off when subproblems shrink fast and combining is cheap.
Counting inversions rides inside merge sort for O(n log n) instead of O(n²).

Quick check

1. What are the three steps of divide and conquer?

2. Which technique analyzes divide-and-conquer running times?

3. Counting inversions with divide and conquer runs in:

4. When does divide and conquer NOT help?

The template in hand, let's meet the famous algorithms it produces. Next up: Module 12 — Divide & Conquer in Action.