\documentclass{bschlangaul-aufgabe}
\bLadePakete{syntax,sortieren,mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe zum Mergesort},
  Thematik = {Mergesort},
  Referenz = 46115-2018-F.T1-A6,
  RelativerPfad = Examen/46115/2018/03/Thema-1/Aufgabe-6.tex,
  ZitatSchluessel = examen:46115:2018:03,
  ZitatBeschreibung = {Thema 1 Aufgabe 6},
  BearbeitungsStand = unbekannt,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Mergesort},
  EinzelpruefungsNr = 46115,
  Jahr = 2018,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 6,
}

\section{Aufgabe zum Mergesort
\index{Mergesort}
\footcite[Thema 1 Aufgabe 6]{examen:46115:2018:03}
}

\begin{enumerate}

\item Gegeben ist das folgende Array von Zahlen:\footcite[Seite 2, Aufgabe 4]{aud:pu:2}

\begin{center}
[13, 4, 7, 32, 27, 11, 6, 17, 2]
\end{center}

Sortieren Sie das Array mittels Mergesort aufsteigend von links nach
rechts. Das Aufteilen einer Liste soll in der Mitte erfolgen und, falls
notwendig, die zweite Liste ein Element länger sein als die erste.
Listen der Länge zwei dürfen durch direkten Vergleich sortiert werden.
Geben Sie die Eingabe und das Ergebnis jedes (rekursiven) Aufrufs an.
Geben Sie abschließend die sortierte Liste an.

\begin{bAntwort}
\begin{center}
\def\myNodes{}
\begin{forest}
  /tikz/arrows=->, /tikz/>=latex, /tikz/nodes={draw},
  for tree={delay={sort}}, sort level=2
  [13 4 7 32 27 11 6 17 2
    [13 4 7 32
      [13 4
        [13]
        [4]
      ]
      [7 32
        [7]
        [32]
      ]
    ]
    [27 11 6 17 2
      [27 11
        [27]
        [11]
      ]
      [6 17 2
        [6]
        [17]
        [2]
      ]
    ]
  ]
]
%
\coordinate (m) at (!|-!\forestOnes);
\myNodes
\end{forest}
\end{center}
\end{bAntwort}

\item Beantworten Sie folgende Fragen jeweils ohne Begründung oder
Beweis.

\begin{enumerate}
\item Welche Worst-Case-Laufzeit ($\mathcal{O}$-Notation) hat Mergesort
für n Elemente?

\begin{bAntwort}
$\mathcal{O}(n \cdot log(n))$ im Best-, Average- und Worst-Case
\end{bAntwort}

\item Welche Laufzeit hat Mergesort für $n$ Elemente im Best-Case?

\begin{bAntwort}
$\mathcal{O}(n \cdot log(n))$ im Best-, Average- und Worst-Case
\end{bAntwort}

\item Kann basierend auf paarweisen Vergleichen von Werten schneller
(Laufzeitkomplexität) als Mergesort sortiert werden?

\begin{bAntwort}
Nein. Es lässt sich beweisen, dass ein vergleichsbasiertes
Sortierverfahren nicht schneller als $\Omega (n\cdot \log(n))$ sein
kann.
\bFussnoteUrl{https://de.wikipedia.org/wiki/Sortierverfahren}
\end{bAntwort}
\end{enumerate}
\end{enumerate}
\end{document}