+ % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
+ % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
+ % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
+ % 63:MAX
+ \begin{center}
+ \input{images/32-ec-from-bs64.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
+ 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
+ Schnittmuster ist
+ $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
+ $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
+ 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
+ \label{fig:32-ec-from-bs64}
+\end{figure}
+
+Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen
+Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
+konstruiert haben, kann demnach auch erreicht werden, wenn
+$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
+Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein
+32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden,
+wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode
+konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den
+optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf
+208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte
+Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
+dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
+Verzögerung dieser Sortiernetzwerke gleich ist.
+
+Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
+unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
+gute Schnittmuster anzugeben.
+
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen
+Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
+Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
+Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
+ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
+ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
+die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
+leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
+der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+
+Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
+haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
+von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
+\emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
+$m$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-m)$-Netzwerk.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-ps32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
+ $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-ps32}
+\end{figure}
+
+\subsection{Versuche mit dem Pairwise-Sorting-Netzwerk}
+
+Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
+Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
+\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
+16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
+Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
+$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
+Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+
+Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
+einsetzt und auch nicht auf einem Mischer basiert, ist der
+$\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
+Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
+den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die
+strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die
+Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
+
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
+ \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
+ \end{center}
+ \caption{PS(32) mit 16 Schnitten zu PS(16).}
+ \label{fig:ps16-from-ps32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-pairwise.tex}
+ \end{center}
+ \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
+ ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das
+ resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
+ \label{fig:16-pairwise}