Wie kann ich einen gleichzeitigen Quicksort- oder Mergesort-Algorithmus für Java implementieren?

Wir hatten Probleme auf einem Mac mit 16 (virtuellen) Kernen, bei dem nur ein Kern (!) Mit dem standardmäßigen Java-Sortieralgorithmus arbeitete, und es war auch nicht gut zu sehen, dass diese sehr gute Maschine völlig unbenutzt war. Also haben wir unser eigenes geschrieben (ich habe es geschrieben) und in der Tat gute Beschleunigungen erzielt (ich habe ein Multithread-Quicksort geschrieben und aufgrund seiner Partitionierung lässt es sich sehr gut parallelisieren, aber ich hätte auch ein Mergesort schreiben können) ... Aber meine Implementierung ist nur skalierbar Bis zu 4 Threads, es ist proprietärer Code, und ich würde lieber einen aus einer seriösen Quelle verwenden, anstatt mein neu erfundenes Rad zu verwenden.

Das einzige, was ich im Web gefunden habe, ist ein Beispiel dafür, wienicht Um eine Multithread-QuickSort in Java zu schreiben, wird eine (wirklich schreckliche) Busy-Loop ausgeführt, wobei Folgendes verwendet wird:

while (helpRequested) { }

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

Zusätzlich zum grundlosen Verlust eines Threads muss sichergestellt werden, dass die Perfs durch Besetztschleifen in der While-Schleife (was verblüffend ist) beendet werden.

Daher meine Frage: Kennen Sie eine korrekte Implementierung von Multithread-Quicksort oder Mergesort in Java, die von einer seriösen Quelle stammen würde?

Ich lege den Schwerpunkt auf die Tatsache, dass ich weiß, dass die Komplexität O (n log n) bleibt, aber ich würde es trotzdem sehr genießen, wenn all diese Kerne anfangen zu arbeiten, anstatt im Leerlauf zu laufen. Beachten Sie, dass ich für andere Aufgaben auf demselben Mac mit 16 virtuellen Kernen eine Geschwindigkeitssteigerung von bis zu x7 durch Parallelisierung des Codes festgestellt habe (und ich bin keineswegs ein Experte für Parallelität).

So hart die Komplexität auch bleibt O (n log n), ich würde eine x7 oder x8 oder sogar x16-Beschleunigung wirklich schätzen.