Da PArr und len angepasst werden, sollten sich die einzelnen Threads also nicht in die Quere kommen...
Zumindest liegt das Array in einem zusammenhängenden Speicherbereich, wenn ein Prozessor dort etwas ändert und der andere auf Daten zugreifen will, die im selben Adressegment des eigenen Cache liegen, hat er erst einmal Pause.
Versuchsweise könnte jeder Thread eine Kopie des zu sortierenden Teilarray erstellen, diese Kopie sortieren und zum Schluss zurückschreiben. Allerdings müsste man sicherstellen, das jede Kopie aus Sicht des Cache in einem anderen Adressegment liegt.