🎓 A1Learner
🔍
0 of 112 lessons completed

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

Exercise

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