Structured Parallel Programming

Chapter 13

Merge Sort

In a divide-and-conquer algorithm, either the divide or merge step can sometimes become a bottleneck if done serially. Parallel merge sort demonstrates a case where the merge step can be parallelized to avoid a bottleneck by using divide-and-conquer. The net effect is a divide-and-conquer algorithm running inside a divide-and-conquer algorithm. This illustrates the practical importance of having a parallel framework that supports efficient nested parallelism.

Serial merge sort has two desirable properties:

• It is stable (that is, the order of equal elements is not changed).

• It has guaranteed asymptotic running time O(N lgN).

Weighing against these desirable properties is the disadvantage that merge sort is an out-of-place ...