%% -*- mode: latex; TeX-master: "informatik.tex"; -*-

\begin{slide}{Merge-Sort (Sort)}
\begin{verbatim}
sortiere (Folge a) = 
  wenn Länge (a) <= 1, 
    dann gib a aus, 
    sonst 
      Folge b = (ungefähr) die Hälfte 
            der Elemente von a;
      Folge c = die restlichen Elemente von a;
      Folge b' = sortiere (b)
      Folge c' = sortiere (c);
      füge b' und c' zusammen;
\end{verbatim}

die Ausgabe von sortiere(a) enthält alle Element von a genau einmal
und ist aufsteigend geordnet.

Entwurfsprinzip: Rekursion, divide and conquer

\end{slide}

\begin{slide}{Merge-Sort (Merge)}

\kopf{$ $Id: merge.tex,v 1.2 2006-10-30 16:03:17 waldmann Exp $ $}

b' und c' sind Listen von Elementen (Zahlen)
\begin{verbatim}
füge b' und c' zusammen =
  solange ( b' nicht leer und c' nicht leer ) 
    wenn  erstes (b') < erstes (c')
      dann  ausgabe(erstes (b')); verkürze b';
      sonst ausgabe(erstes (c')); verkürze c';
  gib restliche Elemente von b' aus
  gib restliche Elemente von c' aus
\end{verbatim}
in der Ausgabe stehen alle Element von b' und c' genau einmal.


Anzahl der Vergleiche: $\le$ Länge von b $+$ Länge von c $-$ 1
\end{slide}


\begin{slide}{Merge-Sort (Komplexität)}

Anzahl der Vergleiche? 
\[ T(1)=0, T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2\rceil) + (n-1) \]
Beispiele:
\[
\begin{array}{c|cccccccccc}
  n   & 1 & 2 & 3 & 4 & 5 &  6 &  7 &  8 &  9 \\ \hline
  T(n)& 0 & 1 & 3 & 5 & 8 & 11 & 14 & 17 & 21
\end{array}
\]
Übung: beweise durch Induktion $T(2^k) = 1 + (k-1) \cdot 2^k$.

Mit $n = 2^k$, also $k = \log_2 n$ folgt $T(n) \approx n \log_2 n$.

D. h. Merge-Sort ist asymptotisch besser als Bubble-Sort.

\end{slide}
