Divide-and-conquer algorithm
= 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.