Which sorting method is most suitable for parallel

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

I think Merge Sort would be the best answer here. Because the basic idea behind merge sort is to divide the problem into individual solutions.Solve them and Merge them.

Thats what we actually do in parallel processing too. Divide the whole problem into small unit statements to compute parallely and then join the results. Thanks

Answer 2

i think merge sort

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

Answer 3

It is merge sort since the sorting is done on two sub arrays and they are compared and sorted at the end. these can be done in parallel

Answer 4

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 5

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 6

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