Stufe 1 beginnt, soll 8 Zahlen sortieren,
ruft erstmal Stufe 2 auf mit Paramter 4 (speichere alle lokalen Daten, etwa die 8 Zahlen, dass die Stufe 1
genau 8 Zahlen bearbeteit, dass bisher noch keine sortiert sind usw. in den Stack, dahinter die 4 Zahlen
für die nächste Stufe + die Info dass es genau vier Zahlen sind falls man das nicht direkt aus dem Stack
erkennen kann (z.B. ein festes Trennsymbol nach den 4 Zahlen))
Stufe 2 beginnt, soll 4 Zahlen sortieren (dass muss aus dem Stack irgendwie ersichtlich sein),
ruft erstmal Stufe 3 auf mit Paramter 2 (alle lokalen Daten speichern)
Stufe 3 beginnt, soll 2 Zahlen sortieren,
nimmt die beiden Zahlen von Stack runter und legt sie in der richtigen Reihenfolge zurück
Stufe 2 wieder, (muss jetzt erstmal die lokalen Daten auslesen um zu erkennen ob diese Stufe gerade
erst gerufen wurde oder bereits in der Mitte der Bearbeitung steht, ob also bereits ein oder zweimal
Stufe 3 ausgeführt wurde oder nicht)
Hälfte der 4 Zahlen sind sortiert,
nimmt alle 4 runter, legt die beiden sortierten wieder drauf, die beiden noch unsortieren ganz oben drauf
(voher die lokalen Daten)
und ruft wieder Stufe 3
Stufe 3 beginnt, soll 2 Zahlen sortieren,
nimmt die beiden Zahlen von Stack runter und legt sie in der richtigen Reihenfolge zurück
Stufe 2 wieder, nimmt die 4 vom Stack (die ersten beiden sortiert, die hinteren beiden auch)
(außerdem die lokalen Daten einlesen, daraus erkennt diese Stufe, dass diese 4 Zahlen bereits sortiert sind!)
sortiert nun alle 4 und legt sie in der richtigen Reihenfolge in den Stack
Stufe 1 beginnt, (lokale Daten lesen usw.) die 4 oberen Zahlen im Stack sind sortiert, die unteren 4 nicht,
alle 8 runternehmen, die 4 sortierten nach unten, die 4 unsortierten oben drauf
und Stufe 2 darf wieder genau das gleiche tun..
am Ende alle 8 runter, zusammenmergen und fertig
----------------
umgesetzt wäre das etwa so eine while-Schleife:
while (!fertig) {
1. lese Daten vom Stack, erkenne welche Stufe gerade läuft, welche Zahlen, ob es nur Parameterzahlen sind
oder auch lokale Daten, also ob diese Stufe gerade beginnt oder schon zwischendurch andere aufgerufen hat
2. entscheide was als nächstes zu tun ist und diese Aktion vorbereiten (mögliche Aktionen u.a.: rufe entweder
direkt nächste Stufe, oder sortiere direkt die beiden Zahlen im Stack oder tausche die sortierte mit der
unsortierten Hälfte und rufe zum 2. Mal die nächste Stufe oder merge die beiden sortieren Teilisten zusammen),
am Ende jeweils die lokalen Daten + Parameter für den Aufruf einer höheren Stufe ODER den Rückgabewert
an eine niedrigere Stufe in den Stack schreiben und zur nächsten Runde in der while-Schleife übergehen,
da beginnt dann die nächste Runde
(Spezialfall: falls Ende von Stufe 0 erkannt: Variable fertig auf true setzen)
}
