Divide and Conquer Strategies

Divide and conquer is one of the most powerful algorithm design paradigms in Computer Science. It solves a problem by breaking it into smaller sub-problems of the same type, solving each sub-problem recursively, and then combining the results. At A-Level, you must understand the paradigm, be able to identify algorithms that use it, and analyse their complexity.

---

The Three Steps

Every divide and conquer algorithm follows three steps:

Step	Description	Example (Merge Sort)
Divide	Split the problem into smaller sub-problems	Split the array into two halves
Conquer	Solve each sub-problem recursively	Recursively sort each half
Combine	Merge the results of the sub-problems	Merge the two sorted halves

The recursion terminates at a base case — a sub-problem small enough to solve directly (e.g., an array of size 0 or 1 is already sorted).

---

Algorithms That Use Divide and Conquer