Parallel Computing for Data Science

Chapter 10

Parallel Sorting and

Merging

One of the most common types of computation is sorting, the main subject

of this chapter. A related topic is merging, meaning to combine two sorted

vectors into one large sorted vector.

Sorting is not an embarrassingly parallel operation (Section 2.11). Accord-

ingly, many different types of parallel sorts have been invented. We’ll cover

some introductory material here.

10.1 The Elusive Goal of Optimality

There is a vast literature on sorting methods, including for parallel com-

puting. But the “best” one depends somewhat on the nature of the data,

thus on the nature of the application, and even more on the nature ...