Difference between sequential and parallel divide and conquer

Question

In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy

In divide and conquer, we solve a problem recursively, applying three steps at each level of recursion:

Divide the problem into a number of subproblems that are smaller instances of the same problem

Conquer the subproblems by solving them recursively. If the subproblems sizes are small enough, however, just solve the problems in a straight forward manner.

Combine the solutions into the solution of the original problem.

This algorithmic strategy is assumed on sequential machines and is a non-parallel divide and conquer strategy.

How is parallel divide and conquer different from the above? Which step among divide, conquer, combine will be different?

My assumption is that the dividing step will not change and combine step will not change, but only the conquer step changes and the change will be that each subproblem will be solved in parallel. Is it true?

• Dan D.: Parallel divide and conquer is implemented using what is called fork-join parallelism.

Answer 1

Just like you wrote, you can solve independent subproblems in parallel. Here are two examples:

• In merge sort, you can sort the two halves of the input in parallel, and then merge them together sequentially.

• In quicksort, you split the input into two halves sequentially, and can then sort both of them in parallel.

In the first case there is no divide step, and in the second case there is no conquer step. In other cases probably all three steps will be present.

Some divide-and-conquer approaches have a single subproblem. This is the case in binary search. Such algorithms do not benefit from parallelization.