Erstaunlicherweise läuft dieser Algorithmus bei mehr als 2 Prozessoren bzw. Prozessorkernen nicht nennenswert schneller, also scheint dann schon die Ausgabe "der Flaschenhals" zu sein.
Das ist genau das, was dir Leute versucht haben, mitzuteilen: Ab einem gewissen Punkt bringen mehr Threads nix mehr. Das hat höchstwahrscheinlich nix mit "Ausgabe" zu tun. Das kannst du auch gut nachprüfen: Schalt einfach temporär die Ausgabe aus.
Falls du ein bisschen was über Parallelisierung lernen willst: Füg einen Parameter ein mit dem du steuern kannst, wieviele Threads die Sortierung bearbeiten, und beobachte die Auswirkungen
