Analyse der Laufzeit:

Es werden p Prozessoren verwendet, die jeweils ${\frac{n}{p}}$ Zahlen speichern. Zu Beginn sortiert jeder Prozessor seine Liste in O(${\frac{n}{p}}$ · log ${\frac{n}{p}}$) . Als Pivotelement wird der Median genommen, der bei einer sortierten Liste in konstanter Zeit ermittelt werden kann. Das Broadcasten des Pivotelements dauert in der i -ten Phase k - i + 1 Schritte. Das Aufspalten der Liste bzgl. des Pivotelements erfolgt in O(log ${\frac{n}{p}}$) . Der Transfer benötigt O(${\frac{n}{p}}$) , das Mischen ebenfalls O(${\frac{n}{p}}$) . Also ergibt sich für die parallele Laufzeit

$$\underbrace{O\left ( \frac{n}{p} \cdot \log \frac{n}{p}\right )} \underbrace{O(\log ^{2}p)} \underbrace{O\left ( \frac{n}{p} \cdot \log p\right )}$$ + +

lokales Sortieren Pivot Broadcast Split + Transfer + Merge

Die Kosten betragen daher

Für p $\leq$ n ist der erste und letzte Term O(n · log n) .
Für p $\leq$ n/log n ist der zweite Term O(n · log n) .

Also ist der Algorithmus für bis zu n/log n Prozessoren kostenoptimal.