Sortierung nimmt im seriellen Fall O (n log n). Wenn wir O (n) Prozessoren haben, würden wir auf eine lineare Beschleunigung hoffen. O (log n) -Parallelalgorithmen existieren, sie haben jedoch eine sehr hohe Konstante. Sie sind auch nicht auf Standardhardware anwendbar, die nicht in der Nähe von O (n) -Prozessoren ist. Bei p-Prozessoren sollten sinnvolle Algorithmen eine Zeit von 0 (n / p log n) benötigen.

Im seriellen Fall weist die schnelle Sortierung im Durchschnitt die beste Laufzeitkomplexität auf. Ein paralleler schneller Sortieralgorithmus ist einfach zu implementieren (sieheHie undHie). Es funktioniert jedoch nicht gut, da der erste Schritt darin besteht, die gesamte Sammlung auf einem einzigen Kern zu partitionieren. Ich habe Informationen zu vielen parallelen Sortieralgorithmen gefunden, aber bisher nichts gesehen, was auf einen klaren Gewinner hindeutet.

Ich möchte Listen mit 1 bis 100 Millionen Elementen in einer JVM-Sprache sortieren, die auf 8 bis 32 Kernen ausgeführt wird.