DSA The Divide and Conquer Pattern

Divide and conquer is a pattern that splits a problem into smaller copies of itself. Each copy is solved on its own, and the answers are combined into one answer.

Splitting in half

Splitting cuts a list into two halves. Each half is a smaller copy of the same sorting job.

nums = [8, 3, 7, 1, 9, 2, 6, 4]
mid = len(nums) // 2
print("left:", nums[:mid])
print("right:", nums[mid:])

Combining two sorted halves

Combining merges two sorted lists into one sorted list. The smaller front value moves first each time.

left = [1, 4, 7]
right = [2, 3, 8]
merged = []
i = 0
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
merged += left[i:]
merged += right[j:]
print(merged)

Counting the split levels

Halving 16 items reaches single items in four rounds. The round count is the depth of the split tree.

size = 16
rounds = 0
while size > 1:
    size = size // 2
    rounds += 1
    print("round", rounds, "piece size", size)
print("rounds:", rounds)

Example

members = [
    ("Merge Sort", "split the list", "merge two sorted runs"),
    ("Quicksort", "partition around a pivot", "the pivot lands in place"),
    ("Binary Search", "halve the search range", "the surviving half is the answer"),
]
print("Divide and Conquer")
for name, split, combine in members:
    print(" ", name, "- split:", split, "| combine:", combine)
size = 16
pieces = 1
level = 0
while pieces < size:
    print("level", level, "pieces:", pieces)
    pieces *= 2
    level += 1
print("level", level, "pieces:", pieces)
print("levels of splitting:", level)

Key points

Divide and conquer splits one problem into smaller copies of the same problem.
The split step cuts the input into pieces.
The solve step answers each piece, often by splitting it again.
The combine step merges the piece answers into the final answer.
Splitting in half gives about log n levels of splitting.

In this example, three known algorithms are printed as members of one family. Merge sort splits a list and merges sorted runs. Quicksort partitions around a pivot and needs no merge. Binary search halves a range and keeps one half. The loop then splits 16 items by doubling the piece count each level. Four levels reach 16 single pieces. That depth sits behind the n log n cost of both sorts.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

members = [
    ("Merge Sort", "split the list", "merge two sorted runs"),
    ("Quicksort", "partition around a pivot", "the pivot lands in place"),
    ("Binary Search", "halve the search range", "the surviving half is the answer"),
]
print("Divide and Conquer")
for name, split, combine in members:
    print(" ", name, "- split:", split, "| combine:", combine)
size = 16
pieces = 1
level = 0
while pieces < size:
    print("level", level, "pieces:", pieces)
    pieces *= 2
    level += 1
print("level", level, "pieces:", pieces)
print("levels of splitting:", level)

Exercise

An algorithm splits its input in half, solves each half, and merges the answers. Which pattern is it?

A greedy choice Divide and conquer A sliding window Backtracking