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.
Articles by others on the same topic
Divide-and-conquer is a fundamental algorithm design paradigm characterized by three main steps: 1. **Divide**: The problem is divided into smaller subproblems, ideally of roughly equal size. These subproblems are similar in nature to the original problem but smaller in scope. 2. **Conquer**: Each of the subproblems is solved individually. If the subproblems are still too large or complex, they can be further divided and solved recursively.