<p>The following article (PDF download) is a comparative study of parallel sorting algorithms on various architectures:</p>
<p><a href="http://parasol.tamu.edu/publications/download.php?file_id=191" rel="nofollow noreferrer">Parallel sorting algorithms on various architectures</a></p>
<p>According to the article, <strong>sample sort</strong> seems to be best on many parallel architecture types.</p>
<p>Update to address Mark's concern of age:</p>
<p>Here are more recent articles introducing something more novel (from 2007, which, btw, still get compared with sample sort):</p>
<p><a href="http://gauss.cs.ucsb.edu/publication/psort.pdf" rel="nofollow noreferrer">Improvements on sample sort</a> <br/>
<a href="http://www.dia.eui.upm.es/asignatu/pro_par/articulos/AASort.pdf" rel="nofollow noreferrer">AA-Sort</a></p>
<p>The bleeding edge (circa 2010, some only a couple months old):</p>
<p><a href="http://parlab.eecs.berkeley.edu/wiki/_media/patterns/sortingpattern.pdf" rel="nofollow noreferrer">Parallel sorting pattern</a><br/>
<a href="http://lap.epfl.ch/webdav/site/lap/shared/publications/YeApr10_HighPerformanceComparisonBasedSortingAlgorithmOnManyCoreGpus_IPDPS10.pdf" rel="nofollow noreferrer">Many-core GPU based parallel sorting</a><br/>
<a href="http://cass-mt.pnl.gov/docs/pubs/gpusort-2010-08-25.pdf" rel="nofollow noreferrer">Hybrid CPU/GPU parallel sort</a><br/>
<a href="http://www.cc.gatech.edu/%7Ebader/COURSES/UNM/ece638-Fall2004/papers/HBJ98.pdf" rel="nofollow noreferrer">Randomized Parallel Sorting Algorithm with an Experimental Study</a><br/>
<a href="http://charm.cs.uiuc.edu/charmWorkshop/slides/CharmWorkshop2010_Sorting.pdf" rel="nofollow noreferrer">Highly scalable parallel sorting</a><br/>
<a href="http://www.scipub.org/fulltext/jcs/jcs62163-167.pdf" rel="nofollow noreferrer">Sorting N-Elements Using Natural Order: A New Adaptive Sorting Approach</a><br/></p>
<p><strong>Update for 2013:</strong>
Here is the bleeding edge circa January, 2013. (Note: A few of the links are to papers at Citeseer and require registration which is free):<br/></p>
<p>University lectures:<br/>
<a href="http://www.cs.sunysb.edu/%7Erezaul/Spring-2012/CSE613/CSE613-lecture-9.pdf" rel="nofollow noreferrer">Parallel Partitioning for Selection and Sorting</a><br/>
<a href="http://homepages.math.uic.edu/%7Ejan/mcs572/parallelsorting.pdf" rel="nofollow noreferrer">Parallel Sorting Algorithms Lecture</a><br/>
<a href="http://www.clear.rice.edu/comp422/lecture-notes/comp422-2012-Lecture21-Sorting.pdf" rel="nofollow noreferrer">Parallel Sorting Algorithms Lecture 2</a><br/>
<a href="http://www.redgenes.com/Lecture-Sorting.pdf" rel="nofollow noreferrer">Parallel Sorting Algorithms Lecture 3</a><br/>
<br/>
Other sources and papers:
<br/>
<a href="http://hgpu.org/?p=7227" rel="nofollow noreferrer">A novel sorting algorithm for many-core architectures based on adaptive bitonic sort</a><br/>
<a href="http://charm.cs.illinois.edu/talks/SortingIPDPS10.pdf" rel="nofollow noreferrer">Highly Scalable Parallel Sorting 2</a><br/>
<a href="http://www.economyinformatics.ase.ro/content/EN4/alecu.pdf" rel="nofollow noreferrer">Parallel Merging</a><br/>
<a href="http://www.drdobbs.com/parallel/parallel-merge/229204454?queryText=parallel%2Bsort" rel="nofollow noreferrer">Parallel Merging 2</a><br/>
<a href="http://arxiv.org/ftp/arxiv/papers/1209/1209.3050.pdf" rel="nofollow noreferrer">Parallel Self-Sorting System for Objects</a><br/>
<a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.252.9314" rel="nofollow noreferrer">Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms</a><br/>
<a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.7866" rel="nofollow noreferrer">Shared Memory, Message Passing, and Hybrid Merge Sorts for Standalone and Clustered SMPs</a><br/>
<a href="http://pages.videotron.com/aminer/" rel="nofollow noreferrer">Various parallel algorithms (sorting et al) including implementations</a><br/>
<br/>
GPU and CPU/GPU hybrid sources and papers:
<br/>
<a href="http://hgpu.org/?p=8085" rel="nofollow noreferrer">An OpenCL Method of Parallel Sorting Algorithms for GPU Architecture</a><br/>
<a href="http://hgpu.org/?p=8198" rel="nofollow noreferrer">Data Sorting Using Graphics Processing Units</a><br/>
<a href="http://hgpu.org/?p=8031" rel="nofollow noreferrer">Efficient Algorithms for Sorting on GPUs</a><br/>
<a href="http://hgpu.org/?p=1203" rel="nofollow noreferrer">Designing efficient sorting algorithms for manycore GPUs</a><br/>
<a href="http://hgpu.org/?p=1422" rel="nofollow noreferrer">Deterministic Sample Sort For GPUs</a><br/>
<a href="http://hgpu.org/?p=3331" rel="nofollow noreferrer">Fast in-place sorting with CUDA based on bitonic sort</a><br/>
<a href="http://hgpu.org/?p=923" rel="nofollow noreferrer">Fast parallel GPU-sorting using a hybrid algorithm</a><br/>
<a href="http://hgpu.org/?p=8602" rel="nofollow noreferrer">Fast Parallel Sorting Algorithms on GPUs</a><br/>
<a href="http://hgpu.org/?p=1533" rel="nofollow noreferrer">Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort</a><br/>
<a href="http://hgpu.org/?p=892" rel="nofollow noreferrer">GPU sample sort</a><br/>
<a href="http://hgpu.org/?p=2033" rel="nofollow noreferrer">GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures</a><br/>
<a href="http://hgpu.org/?p=1177" rel="nofollow noreferrer">GPUTeraSort: high performance graphics co-processor sorting for large database management</a><br/>
<a href="http://hgpu.org/?p=4182" rel="nofollow noreferrer">High performance comparison-based sorting algorithm on many-core GPUs</a><br/>
<a href="http://hgpu.org/?p=1084" rel="nofollow noreferrer">Parallel external sorting for CUDA-enabled GPUs with load balancing and low transfer overhead</a><br/>
<a href="http://hgpu.org/?p=6687" rel="nofollow noreferrer">Sorting on GPUs for large scale datasets: A thorough comparison</a><br/></p>
<p><strong>Update for 2022</strong>: I have not forgotten this answer and like all things computer related, it has not aged well. I will do my best to update and refresh it for current trends as well as the state of the art, at some point prior to the end of this year (2022). If you have interest in this topic and would like to see the update sooner, please either reply to or better yet, upvote the <em>comment I made below this answer</em>, so that I can gauge interest in this topic over others that also are in need of an update.</p>
Which parallel sorting algorithm has the best average case performance?
<p>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) time.</p>

<p>In the serial case, quick sort has the best runtime complexity on average. A parallel quick sort algorithm is easy to implement (see <a href="https://stackoverflow.com/questions/1897458/parallel-sort-algorithm">here</a> and <a href="https://stackoverflow.com/questions/1784028/which-sorting-method-is-most-suitable-for-parallel-processing">here</a>). 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.</p>

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