+Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
+Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
+weniger Vergleichen aus als der {\em bitone Mischer}, der im
+Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde.
+
+Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
+Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
+sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
+$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
+$W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
+\begin{equation}
+w_i = \left\{ \begin{array}{ll}
+ u_i, & i < n \\
+ v_{i-n}, & i \geqq n
+ \end{array} \right.,
+ \quad 0 \leqq i < N
+\end{equation}
+
+\begin{figure}
+ \begin{center}
+ \input{images/oe-merge.tex}
+ \end{center}
+ \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
+ bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
+ aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
+ \label{fig:oe-merge}
+\end{figure}
+
+Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine
+Liste der geraden Indizes und je eine Liste der ungeraden Indizes.
+\begin{eqnarray}
+ U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
+ U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
+ V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
+ V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
+\end{eqnarray}
+
+Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
+ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
+rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
+Ausgang der Mischer die Folgen
+\begin{eqnarray}
+ W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
+ W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
+\end{eqnarray}
+ergeben.
+
+Anschließend werden die Komparatoren zwischen benachbarten Leitungen
+hinzugefügt,
+\begin{equation}
+ w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
+\end{equation}
+die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
+Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
+
+Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
+Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
+entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
+offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
+Aufbau lauten:
+\begin{itemize}
+ \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
+ \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
+ einzelnen Komparator.
+\end{itemize}
+
+Dass die resultierende Folge sortiert ist, lässt sich mit dem
+{\em 0-1-Prinzip} leicht zeigen:
+Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
+Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
+gleich der Anzahl der Nullen in den ungeraden Teilfolgen
+$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ -- die Einsen verhalten
+sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
+$W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
+\begin{eqnarray}
+ \left|W_{\textrm{gerade}}\right|_0
+ &=& \left|U_{\textrm{gerade}}\right|_0
+ + \left|V_{\textrm{gerade}}\right|_0
+ = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
+ + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
+ \left|W_{\textrm{ungerade}}\right|_0
+ &=& \left|U_{\textrm{ungerade}}\right|_0
+ + \left|V_{\textrm{ungerade}}\right|_0
+ = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
+ + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
+\end{eqnarray}
+Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
+als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
+Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
+wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als
+$W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
+sortieren. Die jeweiligen Situationen sind in
+Abbildung~\ref{fig:oe-post-recursive} dargestellt.
+
+\begin{figure}
+ \centering
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
+ \qquad
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
+ \qquad
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
+ \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
+ kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
+ Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
+ letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
+ sortiert ist.}
+ \label{fig:oe-post-recursive}
+\end{figure}
+
+\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
+
+Auch beim {\em Odd-Even-Mergesort-Netzwerk} -- wie beim {\em bitonen
+Mergesort-Netzwerk} -- entsteht das Sortiernetzwerk aus dem {\em
+Odd-Even-Mischer} durch resursives Anwenden auf einen Teil der Eingabe
+(üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
+Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.