Divide and Conquer


The problem at hand is divided into smaller sub-problems, which are subsequently solved individually in the divide and conquer method. We may eventually reach a point where no more division is conceivable if we continue to divide the subproblems into smaller sub-problems. The smallest possible sub-problems (fractions) are solved at the "atomic" level. The solutions to all sub-problems are then integrated to produce the solution to the main problem.

The divide-and-conquer strategy can be broken down into three steps.

Divide/Break

Breaking the problem down into smaller subproblems is the next stage, and Sub-problems should be a subset of the main problem. This stage recursively divides the issue until no further sub-problems can be divided. Sub-problems become atomic in nature at this point, but they still represent a portion of the more significant problem.

Conquer/Solve

This stage is tasked with resolving a slew of lesser sub-problems. At this level, problems are usually considered 'solved' independently.

Merge/Combine

When the smaller subproblems are addressed, this stage recursively combines them until the original problem is solved. This algorithmic approach is recursive, and the conquer and merge phases are so close together that they appear to be one.

Examples

The divide-and-conquer programming approach is used in the following computer algorithms.

  • Merge Sort
  • Quick Sort
  • Binary Search
  • Strassen's Matrix Multiplication
  • Closest pair (points)

There are numerous approaches to solving any computer problem, but the ones listed above are an excellent example of a divide and conquer strategy.