Какой алгоритм параллельной сортировки имеет наилучшую среднюю производительность?

Сортировка занимает O (n log n) в последовательном случае. Если у нас будет O (n) процессоров, мы будем надеяться на линейное ускорение. Существуют параллельные алгоритмы O (log n), но они имеют очень высокую константу. Они также не применимы к обычному оборудованию, у которого нет даже около O (n) процессоров. С процессорами p разумные алгоритмы должны занимать время O (n / p log n).

В последовательном случае быстрая сортировка имеет в среднем лучшую сложность выполнения. Параллельный алгоритм быстрой сортировки легко реализовать (см. здесь и здесь ). Однако это плохо работает, поскольку самый первый шаг - разделить всю коллекцию на одном ядре. Я нашел информацию о многих алгоритмах параллельной сортировки, но до сих пор я не видел ничего, указывающего на явного победителя.

Я ищу сортировку списков от 1 до 100 миллионов элементов на языке JVM, работающем на 8-32 ядрах. .