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