Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:start [26.02.2024 10:27] – [Schritt für Schritt] Marco Kuemmel | faecher:informatik:oberstufe:algorithmen:sortieren:mergesort:start [26.02.2024 11:00] – [Tabelle] Marco Kuemmel | ||
---|---|---|---|
Zeile 9: | Zeile 9: | ||
====== Schritt für Schritt ====== | ====== Schritt für Schritt ====== | ||
- | | Split-Phase: | + | | **Split-Phase**: Das Array ist noch zu lang. Es wird mehrfach an der (abgerundeten) Hälfte halbiert, bis jedes Teilarray nur noch die Länge 1 hat. | {{ : |
- | | Jedes Teilarray muss nochmal gesplittet werden... | + | | Jedes Teilarray muss nochmal gesplittet werden... |
- | | Das hinterste Teilarray hat noch immer die Länge 2. Daher muss es nochmals halbiert werden. Damit ist das Ende der Split-Phase erreicht. | + | | Das hinterste Teilarray hat noch immer die Länge 2. Daher muss es nochmals halbiert werden. |
+ | | **Merge-Phase** (Verschmelzungsphase): | ||
+ | | Die beiden äußeren Teilarrays werden nun korrekt zusammengefügt. | ||
+ | | Als letzter Merge-Schritt müssen nur noch die beiden letzten Teilarrays zusammengefügt werden. \\ Hier ist gut sichtbar: man muss immer nur die beiden verbleibenden vordersten (=kleinsten) Zahlen der beiden Teilarrays miteinander vergleichen, |