Divide and conquer was a successful military strategy long before it became an algorithm design paradigm. Generals observed that it was easier to defeat one army of 50,000 men, followed by another army of 50,000 men than it was to beat a single 100,000 man army. Thus the wise general would attack so as to divide the enemy army into two forces and then mop up one after the other.
To use divide and conquer as an algorithm design technique, we
must divide the problem into two smaller subproblems, solve each of them
recursively, and then meld the two partial solutions
into one solution to the full problem.
Whenever the merging takes less time than solving the two subproblems,
we get an efficient algorithm.
Mergesort, discussed in Section 
, is the classic example
of a divide-and-conquer algorithm.
It takes only linear time to merge two sorted lists of n/2 elements
each of which was obtained in 
time.
Divide and conquer is a design technique with many important algorithms to its credit, including mergesort, the fast Fourier transform, and Strassen's matrix multiplication algorithm. However, with the exception of binary search, I find it to be a difficult technique to apply in practice. Therefore, the examples below will illustrate binary search and its variants, which yield simple algorithms to solve a surprisingly wide range of problems.