ArraySort(A,0,n-1) sortiert Array A der Länge n aufsteigend.\\
IA: ($n=2$)\\
ArraySort$(A,0,1)$ wird ausgeführt und  $A[0]$ und $A[1]$ werden vertauscht falls diese an der falschen Position waren. Nun ist $A$ ist aufsteigend sortiert und unser Induktionsanfang gilt.\\

IV: ArraySort$(A,0,n-2)$ sortiert Array $A$ der Länge $n-1$ aufsteigend.\\

IS: ($n-1 \rightarrow n$)\\
ArraySort$(A,0,n-1)$ wird ausgeführt. \\
Fallunterscheidung:\\
Fall 1 (n=1 oder n=2):\\
Falls n=1, beihnaltet das Array nur ein Element und ist damit automatisch sortiert.
Falls n=2, wird das Array $A$ laut IV korrekt sortiert.\\
Fall 2 ($n>2$):\\
Es wird $k=\lfloor \frac{j - i + 1}{3} \rfloor$ berechnet.\\
Nun können wiederum folgende Fälle eintreten:\\

Fall 1: $(n=3, k=1$)\\
ArraySort$(A,0,n-2)$ wird aufgerufen.\\
Aus der IV folgt, dass die vorderen zwei Drittel nun aufsteigend sortiert sind. Alle Zahlen im zweiten Drittel sind also größer als diese im ersten Drittel.\\
ArraySort$(A,1,n-1)$ wird aufgerufen.
Es werden die letzten beiden Drittel sortiert. Da im zweiten Drittel bereits das größere Drittel an Zahlen war, können ohnehin nur solche aus dem zweiten Drittel überhaupt größer als 2/3 aller Zahlen sein und damit in den 3. Teil des Arrays sortiert werden. Somit wären nun im letzten Drittel alle größten Zahlen.
Dass es tatsächlich sortiert ist, garantiert, dass ArraySort$(A,1,n-1)$ mit Indexverschiebung das Gleiche ist, wie ArraySort$(A',0,n-2)$, von dem wir wissen, dass es korrekt sortiert.\\
ArraySort$(A,0,n-2)$ sortiert nun nochmal die ersten zwei Drittel. Da nun sowohl die ersten beiden Drittel, als auch das Letzte aufsteigend sortiert ist, ist ganz $A$ aufsteigend sortiert.\\\\

Fall 2: ($n=4,\ k=1$)\\
ArraySort$(A,0,n-2)$ wird aufgerufen.\\
Aus der IV folgt, dass die vorderen zwei Drittel nun aufsteigend sortiert sind. Alle Zahlen im zweiten Drittel sind also größer als diese im ersten Drittel.\\
ArraySort$(A,1,3)$ wird aufgerufen und ist wie vorher gleich zu ArraySort$(A',0,2)$. Bei dieser Operation ist jedoch $n=3$ und $k=1$. Daraus folgt Fall 1. Es stehen nun wieder alle großen Elemente im letzten Drittel von $A$ und durch den letzten Durchlauf ArraySort$(A,0,n-2)$ ist $A$ aufsteigend sortiert.\\

Fall 3: ($n=5,\ k=1$)\\
ArraySort$(A,0,n-2)$ ist wie in Fall 2 nach der Voraussetzung aufsteigend sortiert. ArraySort$(A,1,4)$ wird aufgerufen und ist gleich zu ArraySort$(A',0, 3)$. Da  $n=4$ und $k=1$ gitl tritt wiederum Fall 2 ein. Die letzte Operation von  ArraySort$(A,0,n-2)$ sortiert wieder das letzte Drittel welchse mit den größten Zahlen gefüllt war. $A$ ist somit aufsteigen sortiert.\\

Fall 4: ($n>5,\ k>1$)
ArraySort$(A,0,n-1-k)$ bestimmt ein neues $k$ . Dieses ist nach dem Algorithmus jedoch kleiner als das vorherige und somit tritt einer der vorherigen Fälle ein, welcher die Teilarrays aufsteigend sortiert,  oder Fall 4 selber tritt noch mal ein und es wir ein weiteres kleineres k bestimmt.
Es kann also nur zu Fall 1-3 führen und damit ist $A$ wieder aufsteigen sortiert.
%  es UNUMGÄNGLICH UND UNWIEDERRUFBAR