201_mergesort.tex

\section{Mergesort}
Diese Sortierverfahren ist ein Paragon der sogenannten \emph{divide et impera}-Strategie.

Ausgehend von einem linearen Feld $\mathcal{A}$ der Größe $n$ unterteilen wir das Problem rekursiv immer weiter in kleinere Probleme,
welche superlinear schneller gelöst werden können. Der Basisfall, ein Array mit einem einzigen Element, ist dann immer
sortiert. Im letzen Schritt vereinen wir alle sortierten Teilarrays zu einem großen sortierten Array. Siehe Abbildung
\ref{fig:mergesort_diagram} für ein Beispiel.

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.8\textwidth]{bilder/mergesort_diagram}
  \caption{Ein Beispiellauf des \texttt{mergesort}-Algorithmus auf den Input $\mathcal{A} = (38,27,43,3,9,82,10)$}
  \label{fig:mergesort_diagram}
\end{figure}
Im folgenden Pseudocode verwenden wir die Funktion $\texttt{Array}(n)$, welches uns einfach nur ein leeres (also z.B.
mit $0$ gefülltes) Array der Länge $n$ gibt, sowie die Funktion $\texttt{len}(\mathcal{A})$, welche die Länge des arrays $\mathcal{A}$
zurückgibt.

\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{\texttt{mergesort}($\mathcal{A}$)}
  \KwIn{An  array $\mathcal{A}$ of size $n$}
  \KwOut{The sorted array $\mathcal{A}$}
  \eIf{$n = 1$}{
    \Return $\mathcal{A}$ \;
  }{
    $k \leftarrow \floor*{\frac{n}{2}}$ \;
    \KwRet $\texttt{merge}(\texttt{mergesort}(\mathcal{A}[0,\dots, k]), \texttt{mergesort}(\mathcal{A}[k+1, \dots,  n]))$
  }
\end{algorithm}

Wobei \texttt{merge} folgendermaßen definiert wird:

\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{\texttt{merge}($\mathcal{A}_1, \mathcal{A}_2$)}
  \KwIn{Two sorted arrays $\mathcal{A}_1$ and $\mathcal{A}_2$}
  \KwOut{The sorted union array $\mathcal{A}$ of the input}
  $\mathcal{A} \leftarrow \texttt{Array}(\texttt{len}(\mathcal{A}_1) + \texttt{len}(\mathcal{A}_2))$ \;
  $i_1, i_2 \leftarrow 0$ \;
  \For{$i \leftarrow 0$ \KwTo $\texttt{len}(\mathcal{A})$}{
    \eIf{$\mathcal{A}_1[i_1] \leq \mathcal{A}_2[i_2]$}{
      $\mathcal{A}[i] \leftarrow \mathcal{A}_1[i_1]$ \;
      $i_1 \leftarrow i_1 + 1$ \;
    }{
      $\mathcal{A}[i] \leftarrow \mathcal{A}_2[i_2]$ \;
      $i_2 \leftarrow i_2 + 1$ \;
    }
  }
  \KwRet $\mathcal{A}$
\end{algorithm}

\subsubsection{Laufzeit}
Die Laufzeit der Algorithmen ist nicht vom konkreten Input, sondern nur von der Länge des Inputs abhängig. Worst, best
und average case sind also gleich. Für \texttt{merge} ist die Länge des Inputs $n = \texttt{len}(\mathcal{A}_1) +
\texttt{len}(\mathcal{A}_2)$ und es gilt: $T_{\text{m}} = T_{\texttt{merge}} = f \in \mathcal{O}(n)$, da Zeile~3 alles dominiert. 

Damit ist die Laufzeitfunktion für \texttt{mergesort} für $T_\text{ms}(1) \in \mathcal{O}(1)$ und für $n > 1$
\[
  T_{\text{ms}}(n) = 2 T_{\text{ms}}(\frac{n}{2}) + T_{\text{m}}(n) + d,
\]
wobei $d \in \mathcal{O}(1)$.
Mit dem Hauptsatz der Laufzeitfunktionen haben wir damit Fall 2, die asymptotisch exakte Laufzeit beträgt ($\log_2{2} = 1$) also
\[
  T^{\text{ms}} \in Θ(n \log{n}).
\]

Um die Methodik der rekursiven Laufzeitberechnungen zu demonstrieren, berechnen wir die eine Seite der Abschätzung
elementar. Um den Beweis übersichtlicher zu halten, nehmen wir an, dass $n=2^k$ für ein $k \in \mathbb{N}$. Für Werte
von $n$, welche keine Zweierpotenz sind, können wir aufgrund der Monotonie von $T_\text{ms}$ dann abschätzen.

\begin{align*}
  T_{\text{ms}} 
  &= 2T_\text{ms}\left(\frac{n}{2}\right) + T_\text{m}(n) + d \\
  &= 4T_\text{ms}\left(\frac{n}{4}\right) + 2 T_\text{m}\left(\frac{n}{2}\right) + 2d + T_\text{m}(n) + d \\
  &= 8T_\text{ms}\left(\frac{n}{8}\right) + 4 T_\text{m}\left(\frac{n}{4}\right) + 4d + 2 T_\text{m}\left(\frac{n}{2}\right) + 2d + T_\text{m}(n) + d \\
  &\vdots \\
  &= \underbrace{n T_\text{ms}(1)}_{\in \mathcal{O}(n)} 
    + \sum_{l=0}^{\log_2 \left(\frac{n}{2}\right)} 2^l T_\text{m}\left(\frac{n}{2^l} \right) 
    + \underbrace{\sum_{l=0}^{\log_2 \left(\frac{n}{2}\right)} 2^l d}_{\in \mathcal{O}(n)}
\end{align*}

Wir müssen also nurnoch den asymptotischen Aufwand für die rekursiven Aufrufe von $T_\text{m}$ finden.
Wir wissen, da $T_\text{m} \in \mathcal{O}(n)$, dass es ein $n_0 \in \mathbb{N}$ und $c \in \mathbb{R}$ gibt, sodass
$T_\text{m}(n) \leq c n$ für \emph{alle} $n > n_0$. Insbesondere also für die nächstgrößere Zweierpotenz, sodass wir
o.B.d.A. annehmen können: $n_0 = 2^k_0$ für ein $k_0 \in \mathbb{N}$. Für alle $n \leq n_0$ können wir den Aufwand von
$T_\text{m}(n)$ zudem durch die Konstante $m = \max(\{T_\text{m}(i) | i \in \{0, \dots, n_0\}\})$ abschätzen.

Das erlaubt es uns, obige Summe aufzuspalten:
\[
  \sum_{l=0}^{k-1} 2^l T_\text{m}\left( \frac{n}{2^l} \right) = 
  \sum_{l=0}^{k-k_0} 2^l T_\text{m}\left( \frac{n}{2^l} \right) + 
  \underbrace{\sum_{l=k-k_0+1}^{k-1} 2^l T_\text{m}\left( \frac{n}{2^l} \right)}_{\leq 2^k m \in \mathcal{O}(n)}.
\]
Es bleibt noch der erste Teil. Aber hier greift endlich die Abschätzung $T_\text{m}(n)~\leq~cn$, und damit
\[
  \sum_{l=0}^{k-k_0} 2^l T_\text{m}\left( \frac{n}{2^l} \right) 
  = c \sum_{l=0}^{k-k_0} 2^l \frac{n}{2^l} 
  = c \sum_{l=0}^{k-k_0} n
  \in \mathcal{O}(n \log_2 n).
\]
Dieser Term dominiert also alle anderen Terme, und damit $T_\text{ms} \in \mathcal{O}(n \log n)$.


\subsubsection{Speicherverbrauch}
In der hier vorgestellten Variante muss bei jedem Aufruf von \texttt{merge} ein neues Array angelegt werden. Damit braucht
$\texttt{mergesort}$ asymptotisch $\mathcal{O}(n)$ zusätzlichen Speicher.

Es gibt allerdings auch weiterentwicklungen, die mit $\mathcal{O}(1)$ Speicher auskommen (z.B. TimSort oder blocksort).