= Divide-and-conquer algorithm
{wiki}
A <divide-and-conquer algorithm> divides a problem into smaller instances, solves them using <recursion>, and combines their answers. In <merge sort>, the division makes two contiguous halves, and the <merge algorithm> combines the resulting <sorted arrays>. The important design step is finding a combination rule cheaper than solving the whole problem afresh.
Halving the <input> is only one part of the design. The number of <recursive calls> and the work outside those calls determine whether the smaller instances actually save time. <Divide-and-conquer combination cost> keeps these quantities separate; the <divide-and-conquer product ledger> shows how an algebraic identity changes the number of required calls in <Karatsuba multiplication>.
For <algorithm correctness>, specify the meaning of each returned answer, prove the <base cases>, and show that combining correct smaller answers gives the required <output>. <Induction> then proves correctness, provided every <recursive call> progresses towards a <base case>. The combination rule must reconstruct everything the caller needs: two sorted halves alone are not a <sorted array>, and four digit blocks alone are not their <integer> product.
Back to article page
