\( \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{\rank}{\textnormal{rank}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \)

Wir kommen auf unsere Gadget-Metapher zurück. Zum Sortieren verwenden wir ein Minmax-Gate, dass zwei Inputs und zwei Outputs hat:

Aus diesem Minmax-Gate wollen wir einen Schaltkreis bauen, der Sortieren kann. Das nennt man in diesem Zusammenhang ein Sortiernetzwerk. Wir folgen der Idee von Mergesort: wir zerlegen die Eingabeliste in zwei Teile, die wir rekursiv sortieren; dann rufen wir eine Prozedur merge auf, die die zwei sortierten Teillisten $X$ und $Y$ zu einer großen sortierten Liste $Z = \texttt{merge}(X,Y)$ zusammenfügt. Sequentiell ist die Prozedur merge einfach zu implementieren und tätigt im Worst-Case $|X| + |Y| - 1$ Vergleiche. Parallel ist das schon schwieriger. In diesem Teilkapitel beschreiben wir Batchers Odd-Even Merging Network und das mergesort-artige Sortiernetzwerk, das man daraus erhält.

Ein Netzwerk für Merge

Wir haben als Input zwei Listen gegeben: $X = [x_1, x_2, \dots, x_n]$ und $Y = [y_1, y_2, \dots, y_n]$. Beide sind bereits sortiert. Wir wollen nun eine sortierte version der Vereinigung, also von $[x_1, \dots, x_n, y_1, \dots, y_n]$ berechnen. Sequentiell kennen Sie das als die Subroutine merge von MergeSort, zum Beispiel aus Kapitel 2.3 von TI-1. Um es parallel berechnen zu können, zerlegen wir das Array $X$ in die ungeraden und die geraden Indizes:

\begin{align*} X_{\rm odd} := [x_1, x_3, x_5, \dots, x_{n-1}] \\ X_{\rm even} := [x_2, x_4, x_6, \dots, x_n] \ , \end{align*}

wobei wir davon ausgehen, dass $n$ gerade ist. Das dient zum Großteil dazu, die Notation zu vereinfachen. Nach gleichem Schema zerlegen wir $Y$:

\begin{align*} Y_{\rm odd} := [y_1, y_3, y_5, \dots, y_{n-1}] \\ Y_{\rm even} := [y_2, y_4, y_6, \dots, y_n] \ , \end{align*}

Nun führen wir rekursiv einen Merge auf $X_{\rm odd} \cup Y_{\rm odd}$ durch, ebenso auf $X_{\rm even} \cup Y_{\rm even}$.

Wir erhalten also

\begin{align*} U := [u_1, u_2, \dots, u_n] & = \texttt{merge}(X_{\rm odd}, Y_{\rm odd})\\ V := [v_1, v_2, \dots, v_n] & = \texttt{merge}(X_{\rm even}, Y_{\rm even}) \end{align*}

Jetzt müssen wir uns noch parallel aus $U$ und $V$ den Merge der Gesamtliste $X \cup Y$ zusammenbasteln - und zwar parallel. Wir können zum Beispiel bereits mit Sicherheit sagen, dass $u_1$ das kleinste dieser Liste ist. Danach wird es schon schwieriger.

Definition(Rang). Sei $Z = X \cup Y$ die Menge der Elemente in der Gesamtliste (wir gehen davon aus, dass kein Element doppelt vorkommt, um den Mengenbegriff bequem verwenden zu können). Der Rang eines Elements $s$ in $Z$ ist die Anzahl der Elemente $z$ mit $z \leq s$, also:

\begin{align*} \rank(s,Z) := \left| \left\{ z \in Z \ | \ z \leq s \right\} \right | \end{align*}

So hat das Minimum von $Z$ zum Beispiel Rang $1$ und das Maximum Rang $2n$.

Wir fragen uns nun: was ist der Rang von $u_i$, also einem Element, das in $X$ auf einer ungeraden Position stand oder in $Y$. Das können wir nicht sicher sagen, zum Beispiel kann $u_2$ Rang 2 haben, aber auch Rang 3, wenn zum Beispiel $u_1 \lt v_1 \lt u_2$ gilt. Kann es Rang 4 haben? Das nächste Lemma beantwortet diese Frage:

Lemma $\rank(u_i) \in \{2i-2, 2i-1\}$.

Beweis. Das Element $u_i$ ist in $X_{\rm odd} \cup Y_{\rm odd}$ enthalten. Dort gibt es genau $i$ Elemente, die $\leq u_i$ sind. Schauen wir uns an, wo $u_i$ in $X$ und $Y$ liegt. Seien $2k-1$ und $2l-1$ die größten ungeraden Indizes mit $x_{2k-1} \leq u_i$ und $y_{2l-1} \leq u_i$. Dann gilt

\begin{align*} x_1 \lt x_2 \lt x_3 \lt \dots \lt x_{2k-1} \leq u_i \\ y_1 \lt y_2 \lt y_3 \lt \dots \lt y_{2l-1} \leq u_i \ . \end{align*}

Die Mengen $X$ und $Y$ enthalten zusammen mindestens $2k-1+2l-1$ Elemente, die $\leq u_i$ sind, und somit gilt $\rank(u_i, Z) \geq 2k + 2l - 2$. Davon gehören $k$ zu $X_{\rm odd}$ und $l$ zu $Y_{\rm odd}$, und somit gilt $k + l = \rank(u_i, X_{\rm odd} \cup Y_{\rm odd}) = \rank(u_i, U) = i$. Zusammen schließen wir, dass $\rank(u_i, Z) \geq 2i - 2$.

Folgende Elemente sind echt größer als $u_i$:

\begin{align*} u_i & \lt x_{2k+1} \lt x_{2k+2} \lt \dots \lt x_n\\ u_i & \lt y_{2l+1} \lt y_{2l+2} \lt \dots \lt y_n \end{align*}

Das sind insgesamt $n-2k + n-2l = 2n - 2i$ Elemente, die größer sind als $u_i$. Betrachten wir noch $x_{2k-1}$ und $y_{2l-1}$. Eines davon ist $u_i$ selbst, und somit ist eines von $x_{2k}, y_{2k}$ echt größer als $u_i$. Es gibt also mindestens $2n-2i+1$ Elemente, die echt größer sind als $u_i$, und somit ist $\rank(u_i) \leq 2i-1$. \(\square\)

Lemma $\rank(v_i) \in \{2i, 2i+1\}$.

Übungsaufgabe Beweisen Sie das obige Lemma.

Für $i=1$ ergibt das erste Lemma $\rank(u_1) \in \{0,1\}$ und somit $\rank(u_1) = 1$, da ein Rang von 0 unmöglich ist. Analog erhalten wir $\rank(v_n) = 2n$. Für $i=1,\dots,n-1$ wenden nun die beiden Lemmas auf $u_{i+1}$ und $v_i$ an und sehen, dass

\begin{align*} \{\rank(u_{i+1}), \rank(v_i)\} = \{2i, 2i+1\} \end{align*}

gilt. Wir müssen also nur noch $u_{i+1}$ und $v_i$ vergleichen und können bestimmen, welche Elemente $z_{2i}$ und $z_{2i+1}$ in der endgültigen sortierten Liste $Z = [z_1, \dots, z_{2n}]$ sind. Im Überblick erhalten wir folgende rekursive Konstruktion für merge:

Beobachtung Das oben beschriebene Merge-Netzwerk hat $\Theta(n \log n)$ minmax-Gates und Tiefe $\Theta(\log n)$.

Ein Sortiernetzwerk auf Merge-Netzwerken

Um nun ein Array $[x_1, x_2, \dots, x_n]$ der Länge $n$ zu sortieren, gehen wir wieder rekursiv vor. Wir nehmen an, dass $n$ gerade ist, und teilen das Array in zwei Hälften $L = [x_1, \dots, x_{n/2}]$ und $U = [x_{n/2}, \dots, x_n]$. Wir sortieren rekursiv und wenden dann merge auf die Ergebnisliste an.

Theorem Das gerade beschriebene Sortiernetzwerk hat Tiefe $\Theta(\log^2 n)$ und $\Theta(n \log^2 n)$ viele Gates.

Übungsaufgabe Beweisen Sie das Theorem.