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. Here is the 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

i think merge sort

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

Answer 2

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