Wie erreicht ein Algorithmus, der verteilt, diese Verbesserung der Laufzeit und womit bezahlt er diese Verbesserung?

Question

Sortieren durch Verteilen erreicht eine bessere Laufzeitkomplexität als Sortieren durch Vergleichen. Wie erreicht ein Algorithmus, der verteilt, diese Verbesserung der Laufzeit und womit bezahlt er diese Verbesserung?