Divide and conquer

Split the array, sort each half, then merge.

Divide and conquer

Divide and conquer splits a problem into smaller parts, solves each part, then combines the results. Merge sort is the classic example.

We split the array in half, sort each half, then merge the two sorted halves. Each step halves the problem, so the depth is log n.

This structure maps naturally to recursion: the base case is a single-element array, which is already sorted.

Cost of splitting

Splitting the array is cheap: compute mid = (left + right) // 2 and recurse on each half. Splitting itself is O(1).

At each tree level a total of n elements are processed (during merging). With log n levels, total work is O(n log n).

This holds even in the worst case; merge sort always runs in O(n log n).

Exercise Split and list

Write split_half(arr). Split the array at mid = len(arr)//2 and return the tuple (left, right). Print ([4, 2], [7, 1, 9]) with print(split_half([4, 2, 7, 1, 9])).

Show example solution

def split_half(arr):
    # Split the array in half
    mid = len(arr) // 2
    return arr[:mid], arr[mid:]
print(split_half([4, 2, 7, 1, 9]))

Test yourself

How many sorted arrays does the merge step take?
- One
- Two
- Three
- As many as the array size
Show answer

Two — Two

Split point

mid = (left + right) ____

Show answer

mid = (left + right) // 2

Divide and conquer: match the terms

Divide

Split in two
Merge

Sort two halves
Base case

Single element
Cost

O(n log n)

Next lesson: Merge operation

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies