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 ...

Get Structured Parallel Programming now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.