Which parallel sorting algorithm has the best average case performance?

Question

Sorting takes O(n log n) in the serial case. If we have O(n) processors we would hope for a linear speedup. O(log n) parallel algorithms exist but they have a very high constant. They also aren't applicable on commodity hardware which doesn't have anywhere near O(n) processors. With p processors, reasonable algorithms should take O(n/p log n/p) time.

In the serial case, quick sort has the best runtime complexity on average. A parallel quick sort algorithm is easy to implement (see here and here). However it doesn't perform well since the very first step is to partition the whole collection on a single core. I have found information on many parallel sort algorithms but so far I have not seen anything pointing to a clear winner.

I'm looking to sort lists of 1 million to 100 million elements in a JVM language running on 8 to 32 cores.

Answer 1

The following article (PDF download) is a comparative study of parallel sorting algorithms on various architectures:

Parallel sorting algorithms on various architectures

According to the article, sample sort seems to be best on many parallel architecture types.

Update to address Mark's concern of age:

Here are more recent articles introducing something more novel (from 2007, which, btw, still get compared with sample sort):

Improvements on sample sort
AA-Sort

The bleeding edge (circa 2010, some only a couple months old):

Parallel sorting pattern
Many-core GPU based parallel sorting
Hybrid CPU/GPU parallel sort
Randomized Parallel Sorting Algorithm with an Experimental Study
Highly scalable parallel sorting
Sorting N-Elements Using Natural Order: A New Adaptive Sorting Approach

Answer 2

The paper "Comparison of Parallel Sorting Algorithms on Different Architectures" may be a good place for you to start.