Divide-and-Conquer

Divide-and-Conquer is a general algorithm design paradigm:

• Divide: divide the input data $S$ into two disjoint subsets $S_1$ and $S_2$
• Recur: solve the subproblems associated with $S_1$ and $S_2$
• Conquer: combine the solutions for $S_1$ and $S_2$ into a solution for $S$