
\begin{slide}{Sortier-Algorithmen: binäres Einfügen}

Idee: vergleiche mit mittlerem Element
\begin{verbatim}
füge x in a[l .. r] ein = {
  if (l = r) 
  then if x < a[l] 
       then x vor a[l] else x nach a[l]
  else m := mitte von l und r
       if x < a[m] 
       then füge x in a[l .. m - 1] ein
       else füge x in a[m + 1 .. r] ein
}
\end{verbatim}
\emph{Vorsicht:} werden alle Spezialfälle
richtig behandelt? Diskussion im Seminar.---
\emph{Beachte:} hier tun wir so, als ob das Beiseiteschieben
der Elemente nichts kostet. 
\end{slide}
