Многопоточная быстрая сортировка или слияние

Как я могу реализовать параллельный алгоритм быстрой сортировки или слияния для Java?

У нас были проблемы с 16- (виртуальным) ядром Mac, где только одно ядро ​​(!) Работало с использованием алгоритма сортировки Java по умолчанию, и было не очень приятно видеть, что эта очень хорошая машина полностью не используется. Таким образом, мы написали свою собственную (я написал ее), и мы действительно добились хороших ускорений (я написал многопотоковую быструю сортировку и из-за ее природы разбиения она распараллеливалась очень хорошо, но я мог бы также написать сортировку слиянием) ... Но моя реализация только масштабируется до 4 потоков, это собственный код, и я бы предпочел использовать один из авторитетных источников вместо моего заново изобретенного колеса.

Единственный, который я нашел в Интернете, - это пример того, какне чтобы написать многопотоковую быструю сортировку в Java, она занята зацикливанием (что действительно ужасно) с использованием:

while (helpRequested) { }

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

Таким образом, в дополнение к потере одного потока без какой-либо причины, он обязательно убивает перфекты с помощью занятого цикла в цикле while (что ошеломляет).

Отсюда мой вопрос: знаете ли вы о какой-либо правильно многопоточной реализации быстрой сортировки или быстрой сортировки в Java, которая поступила бы из надежного источника?

Я подчеркиваю тот факт, что я знаю, что сложность остается O (n log n), но мне все равно очень приятно было бы увидеть, как все эти ядра начинают работать вместо холостого хода. Обратите внимание, что для других задач на тех же 16 виртуальных ядрах Mac я увидел ускорение до x7 за счет распараллеливания кода (и я ни в коем случае не эксперт по параллелизму).

Таким образом, даже несмотря на то, что сложность остается O (n log n), я действительно оценил бы ускорение x7, x8 или даже x16.

Ответы на вопрос(8)

Ваш ответ на вопрос