Divide and Conquer

Divide and conquer solves one large problem by repeatedly breaking it into smaller subproblems of the same type, solving those subproblems, then combining their answers.

A common template is: split, solve recursively, then merge.

Merge sort is a classic example. Suppose the input is [7, 2, 5, 1]. We split it into [7, 2] and [5, 1], then split again until each piece has one element. A single element is already sorted, so recursion can stop there. We then merge sorted pieces back together: [7] with [2] becomes [2, 7], [5] with [1] becomes [1, 5], and finally [2, 7] with [1, 5] becomes [1, 2, 5, 7].

The important idea is that each recursive call works on a smaller version of the same task, and the merge step converts two solved halves into the full answer.