\section{Die untere Laufzeitschranke für vergleichsbasierte Sortieralgorithmen}

Wir haben in der analyse von \texttt{mergesort} gesehen, dass die worst-case-Laufzeit $\mathcal{O}(n \log n)$ nicht
unterschreitet. Es ist auch die best-case-Laufzeit von \texttt{quicksort}. Schneller als $\mathcal{O}(n)$ kann ein
Sortieralgorithmus sicherlich nicht sortieren: Er muss ja jeden Input mindestens einmal angeschaut haben. Aber geht es,
im worst-case, schneller als $\mathcal{O}(n \log n)$?

Die Antwort ist - für vergleichsbasierte Algorithmen - nein, und wir werden in diesem Kapitel den Beweis dazu skizzieren.

Doch was ist ein vergleichsbasierter Algorithmus?
All unsere bisherigen Sortieralgorithmen verglichen stets zwei Elemente, um ihre entsprechende Reihenfolge untereinander zu
bestimmen. Das impliziert, dass die Elemente eine sogenannte totale Quasiordnung haben mussten;
\begin{definition}[totale Quasiordnung]
  \label{def:totale_Quasiordnung}
  Sei $A$ eine Menge. Eine totale Quasiordnung auf $X$ ist eine binäre Relation $\leq$, für welche gilt:
  \begin{itemize}
    \item $a \leq a$ für alle $a \in A$ (\emph{Reflexifität}).
    \item $a \leq b$ und $b \leq c$ impliziert  $a \leq c$ für alle $a,b,c \in A$ (\emph{Transitivität}).
    \item $a \leq b$ oder $b \leq a$ für alle $a,b \in A$ (\emph{Totalität}).
  \end{itemize}
\end{definition}
Insbesondere erfüllt jede totale Ordnung (also beispielsweise die normale Ordnung auf den ganzen oder reellen Zahlen)
die Axiome der totalen Quasiordnung.
Für eine ``echte'' Quasiordnung betrachten wir $X = \{x,y,z\}$, mit $\leq$ definiert durch $y \leq x$, $y \leq z$, $x \leq z$ und $z \leq x$.
Nun sind $x$ und $z$ ``gleich'', wir benutzen das Symbol $x \equiv z$. Formaler aufgeschrieben: $x \leq z  \land  z \leq
x  \Longrightarrow  x \equiv z$.

Für ein praktisches Beispiel können wir Spielkarten anschauen, die wir allein nach den numerischen Werten ordnen. Dann
ist mit $x = $ Herz 8, $y = $ Herz 7 und $z = $ Pik 8 klar, dass $x \equiv z$, aber nicht unbedingt $x = z$, wie es bei
einer totalen Ordnung der Fall wäre.

Vergleichsbasierte Sortieralgorithmen vergleichen daher nur immer genau zwei Elemente miteinander. Dies geschieht bei
\texttt{quicksort} beispielsweise in Zeile 4 der Partition, oder bei \texttt{mergesort} in Zeile 4 von \texttt{merge}.


\subsection{Beweisskizze}
Wir betrachten im Folgenden die Anzahl der nötigen Vergleiche für das Sortieren des Inputs. Da der Aufwand eines
vergleichsbasierten Sortieralgorithmus mindestens so schnell wächst wie die Anzahl der nötigen Vergleiche, haben wir damit eine
untere Schranke für den zeitlichen Aufwand.

Der Kontrollfluss eines vergleichenden Sortierverfahrens kann mittels
eines sogenannten \emph{Entscheidungsbaummodells} dargestellt werden.
In einem Entscheidungsbaummodell werden alle möglichen und nötigen Entscheidungen dargestellt, um ein
sortiertes lineares Feld zu erhalten. Beispiel: Es liegt eine Sequenz
von 3 Zahlen vor $[a_{1},a_{2},a_{3}]$, ganz konkret also möglicherweise $[5,8,2]$. Dann schaut
der zugehörige Entscheidungsbaum folgendermaßen aus:

\begin{center}
  \includegraphics[scale=0.2]{bilder/Entscheidungsbaummodell}
  \label{fig:Entscheidungsbaum}
\par\end{center}

Die Blätter stellen alle möglichen Permutationen des Inputs dar. Die Anzahl der Blätter ist daher gleich $n!$.

Das worst-case Verhalten eines Algorithmus entspricht dem längsten Ast im
Entscheidungsbaum, die Anzahl der inneren Knoten ist dabei genau die Anzahl der notwendigen Vergleiche.

Ein idealer Sortieralgorithmus enspricht einem vollständigen, ausgeglichenen
Baum. Dadurch wird der längste Ast, also der worst case, minimiert. Die
Höhe beträgt $h \geq \log_2(n!)$. Aber wir haben bereits in einer Übungsaufgabe berechnet, dass gilt:
\[
  h \geq \log_2(n!) \in Θ(n \log n).
\]
Also sind wir damit fertig.

\begin{theorem}
  Für vergleichsbasierte Sortieralgorithmen liegt die worst-case Laufzeit immer in 
  \[
    Ω(n \log_n).
  \]
  \label{theorem:untere_schranke_sortieralgorithmen}
\end{theorem}