\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\rank}{\textnormal{rank}} \)

Wenn wir kein Netzwerk bauen wollen, sondern einen allgemeinen PRAM-Algorithmus zulassen wollen, dann können wir merge einfacher implementieren.

Lemma Gegeben seien zwei sortierte Arrays $L$ und $R$ mit je $n$ Elementen. Mit $2n$ Prozessoren können wir $\texttt{merge}(L,R)$ in $O(\log n)$ Zeit berechnen.

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} \leq x_i \lt y_{j+1}$; in anderen Worten: den Rang $r_i := \rank(x_i, R)$. Hierfür braucht er $\ceil{\log (n+1)}$ Schritte. Nun kann er den Rang von $x_i$ in $L \cup R$ berechnen:

\begin{align*} \rank(x_i, L \cup R) & = \rank(x_i, L) + \rank(x_i, R) \\ & = i + r_i \end{align*}

Nun kopiert er das Element an die passende Stelle des Ergebnis-Arrays: result[$i+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, \dots, P'_n$ die Ränge von jedem $y_i$ in $L$ und kopieren es an die richtige Stelle von result. \(\square\)

Theorem(Naives paralleles Mergesort). Wir können mit $n$ Prozessoren ein Array $A$ der Länge $n$ in Zeit $O(\log^2 n)$ sortieren.

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 \leq t \leq 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 $O(\log 2^t) = O(t)$ Schritte. Insgesamt brauchen wir also

\begin{align*} O(1 +2 + \dots + d) = O(d^2) \end{align*}

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