Three steps

Divide, conquer, combine.

Three steps

Divide and conquer has three steps: divide, conquer, combine.

The problem is split into subproblems, each solved recursively, then results are combined.

This approach is used in classic algorithms like merge sort, quick sort and binary search.

Example: merge sort

Merge sort follows these three steps: split the array in half, sort each half, merge the sorted halves.

This approach gives O(n log n) time; it scales well on large data.

Merge sort is a typical example of divide and conquer; the array splits in two at each level.

Exercise Divide and sum

Write dc_sum(arr). Split the array in half, sum each recursively, then add. Print 10 with print(dc_sum([1, 2, 3, 4])).

Show example solution

def dc_sum(arr):
    # Divide and sum
    if len(arr) <= 1:
        return sum(arr)
    mid = len(arr) // 2
    left = dc_sum(arr[:mid])
    right = dc_sum(arr[mid:])
    return left + right
print(dc_sum([1, 2, 3, 4]))

Test yourself

What is the order of divide and conquer steps?
- Divide, conquer, combine
- Divide, combine, conquer
- Conquer, divide, combine
- Combine, divide, conquer
Show answer

Divide, conquer, combine — Divide, conquer, combine.

Subproblem

mid = len(arr) ____ 2

Show answer

mid = len(arr) // 2

Three steps: match the terms

divide

Split
conquer

Solve
combine

Merge
recursion

Self-call

Next lesson: Recursive structure

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies