Which sorting method is most suitable for parallel processing?

Question

I am now looking at my old school assignment and want to find the solution of a question.

Which sorting method is most suitable for parallel processing?

1. Bubble sort
2. Quick sort
3. Merge sort
4. Selection sort

I guess quick sort (or merge sort?) is the answer.

Am I correct?

Answer 1

Like merge sort, quicksort can also be easily parallelized due to its divide-and-conquer nature. Individual in-place partition operations are difficult to parallelize, but once divided, different sections of the list can be sorted in parallel.

One advantage of parallel quicksort over other parallel sort algorithms is that no synchronization is required. A new thread is started as soon as a sublist is available for it to work on and it does not communicate with other threads. When all threads complete, the sort is done.

http://en.wikipedia.org/wiki/Quicksort

Answer 2

Just a couple of random remarks:

1. Many discussions of how easy it is to parallelize quicksort ignore the pivot selection. If you traverse the array to find it, you've introduced a linear time sequential component.
2. Quicksort is not easy to implement at all in distributed memory. There is a discussion in the Kumar book
3. Yeah, I know, one should not use bubble sort. But "odd-even transposition sort", which is more or less equivalent, is actually a pretty good parallel programming exercise. In particular for distributed memory parallelism. It is the easiest example of a sorting network, which is very doable in MPI and such.

Answer 3

It depends completely on the method of parallelization. For multithreaded general computing, a merge sort provides pretty reliable load balancing and memory localization properties. For a large sorting network in hardware, a form of Batcher, Bitonic, or Shell sort is actually best if you want good O(log² n) performance.

Answer 4

i think merge sort

you can divide the dataset and make parallel operations on them..