Divide and conquer
Introduced
Vocabulary
| English | Meaning |
|---|---|
| merge sort/mɜːdʒ sɔːt/ | Sorting by recursively sorting parts and merging the sorted parts. |
| quicksort | Sorting by partitioning values around a pivot and recursively sorting the partitions. |
Split, solve, combine
- Merge sort splits in half, recurses, merges in $\Theta(n)$: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$. Quicksort moves the work into the partition — the pivot quality decides everything.
{exercise:uni-cs1002-skeleton}
Practice
Binary search recurrence is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
One recursive call, constant combine: Theta(log n).
Quicksort's three worlds
- Balanced pivots: $\Theta(n\log n)$. Sorted input with first-element pivots: $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$.
- Course measurements on the 64-element array: merge 310 comparisons, quicksort 356, sorted-input worst 2080. Randomised pivots make the expected count $2n\ln n \approx 1.39\,n\log_2 n$.
{exercise:uni-cs1002-quicksort}
Practice
Sorted input with first-element pivots costs quicksort —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
T(n) = T(n-1) + n: each partition peels one element.
Two worked patterns
- Maximum subarray by divide and conquer: left best, right best, or the best crossing the middle — the crossing scan is a full pass, so $\Theta(n\log n)$. On $[-2, 1, -3, 4, -1, 2, 1, -5, 4]$ the answer is 6.
- Binary search is the degenerate case: one recursive call, constant combine, $\Theta(\log n)$ — the pattern survives with one branch.
{exercise:uni-cs1002-subarray}
Practice
The maximum subarray of [-2, 1, -3, 4, -1, 2, 1, -5, 4] sums to —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The run 4, -1, 2, 1 sums to 6.