divide and conquer
Divide and conquer is a strategy with three beats: divide the problem into smaller pieces of the same kind, conquer each piece (usually by recursion), and combine the pieces' answers into the answer for the whole. The intuition is that a big problem you can't see your way through often splits into halves that are each just a small version of the original — and once the halves are solved, stitching them together is easy. It is the natural partner of recursion: the "conquer" step is almost always a recursive call on a smaller input, and the base case is a piece small enough to solve directly.
Two classics show the shape. Merge sort divides an array into two halves, recursively sorts each half, then merges the two sorted halves into one sorted whole — and that merge is the clever combine step. Binary search divides the search range in half, throws away the half that cannot contain the target, and recurses on the half that can; here there is no combine step at all, just relentless halving. Both gain their speed from the same source: each level of division cuts the work down, so the number of levels is only about log n.
The cost of a divide-and-conquer algorithm is captured by a recurrence relation — for example T(n) = 2T(n/2) + O(n) for merge sort, read as "to sort n items, sort two halves and spend linear time merging". The master theorem turns such recurrences into a Big-O answer almost by inspection (merge sort comes out at O(n log n)). A word of care: dividing only helps when the subproblems are genuinely smaller and the combine step is cheap. If combining is as expensive as solving from scratch, you gain nothing.
void mergeSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return; // base: 0 or 1 element
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid); // divide + conquer left
mergeSort(a, mid + 1, hi); // divide + conquer right
merge(a, lo, mid, hi); // combine the two sorted halves
}The recurrence T(n) = 2T(n/2) + O(n) gives O(n log n) by the master theorem.
Divide-and-conquer is not the same as dynamic programming. Both break a problem into subproblems, but classic divide-and-conquer subproblems are independent (the two halves of merge sort never overlap), whereas dynamic programming exists precisely to handle subproblems that DO overlap and would otherwise be recomputed.