Divide and conquer
- Algorithms course
- Intermediate
- Lesson 1/80
- 4 min
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).
Practice 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])).
Starter code
def split_half(arr):
# Split the array in halfSample 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]))Expected output
([4, 2], [7, 1, 9])
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 How many sorted arrays does the merge step take?
- One
- Two Correct answer
- Three
- As many as the array size
Explanation: Two
2 Split point
mid = (left + right) ____mid = (left + right) // 2Explanation: // 2 is right.
3 Divide and conquer: match the terms
| Term | Meaning |
|---|---|
Divide |
Split in two |
Merge |
Sort two halves |
Base case |
Single element |
Cost |
O(n log n) |