\begin{slide}{Sortieren durch Einfügen}

\begin{verbatim}
sortiere a[0 .. n-1] = {
  für i von 1 bis n-1 führe aus {
    füge a[i] in a[0 .. i-1] ein
  }
}
\end{verbatim}
 
Invarianten:
\begin{itemize}
\item $(a_0,\ldots,a_{n-1})$ ist eine Permuation von $(A_0,\ldots,A_{n-1})$
\item $a_0 \le a_1 \le \ldots \le a_{i-1}$
\end{itemize}


  
\end{slide}

