Beweis. Sei $L=[x_1,\dots ,x_n]$ und $R=[y_1,\dots ,y_n]$. Wir nehmen an, dass alle Elemente verschieden sind. Wir ordnen jedem Index $i\in \{1,\dots ,n\})$ einen Prozessor $P_i$ zu. Mittels binärer Suche findet $P_i$ das eindeutige $j\in \{0,\dots ,n\}$ mit $y_j\le x_i<y_{j+1}$; in anderen Worten: den Rang $r_i:=\text{rank}(x_i,R)$. Hierfür braucht er $\lceil \log (n+1)\rceil$ Schritte. Nun kann er den Rang von $x_i$ in $L\cup R$ berechnen:

$$\begin{array}{rl}\text{rank}(x_i,L\cup R)& =\text{rank}(x_i,L)+\text{rank}(x_i,R)\\ & =i+j=:r_i.\end{array}$$

Nun kopiert er das Element an die passende Stelle des Ergebnis-Arrays: result[$r_i$] := $x_i$. Dies alles tun die Prozessoren $P_1,\dots ,P_n$ parallel in $O(\log n)$ Schritten. Parallel dazu bestimmen die Prozessoren $P_1^{\prime },\dots ,P_n^{\prime }$ die Ränge von jedem $y_i$ in $L$ und kopieren es an die richtige Stelle von result. $◻$

Beweis. Wir teilen $A$ in zwei Hälften $L$ und $R$ von je $n/2$ Elementen; gleichzeitig teilen wir die Prozessoren in zwei Hälften. Wir sortieren nach gleichem Schema (also rekursiv) die jeweiligen Hälften und führen anschließend merge durch. Wenn die Teilarrays Größe $1$ erreicht haben, sind wir fertig.

Da Rekursion im Zusammenhang von parallelen Algorithmen immer etwas mit Vorsicht zu genießen ist, stellen wir uns den Mergesort-Algorithmus eher als Binärbaum vor, in dem jeder innere Knoten für eine Merge-Operation zuständig ist und jedes Blatt einem Array-Element entspricht:

Besser noch stellen wir es uns als Tabelle mit $n=2^d$ Spalten und $d+1$ Zeilen vor:

Prozessor $P_{12}$ kann anhand seines Indexes $12$ und dem Zeitpunkt $t=3$ leicht errechnen, dass sein Element in dem zweiten von insgesamt vier Achter-Blöcken liegt; dass es sich also um ein "$R$" handelt und sein Element $y$ in diesem den Rang 4 hat. Auch weiß er, dass er mit binärer Suche den Rang von $y$ in $A[1..8]$ bestimmen muss. Mit ein paar einfachen arithmetischen Operationen (oder Bitshifts) von $t$ und $i$ kann er also bestimmen, was zu tun ist.

Laufzeitanalyse. Wir nehmen der Einfachheit halber an, dass $n=2^d$ eine Zweierpotenz ist. Im Schritt $t$ für $1\le t\le d$ werden zwei sortierte Arrays mit je $2^{t-1}$ Elementen mittels merge zu einem Array von $2^t$ Elementen verschmolzen; dafür brauchen wir nach Lemma 3.2.1 $O(\log 2^t)=O(t)$ Schritte. Insgesamt brauchen wir also

$$\begin{array}{r}O(1+2+\cdots +d)=O(d^2)\end{array}$$

Schritte. Die Zeitkomplexität ist somit $O({\log }^{2}n)$.$◻$