Mergesort

Bing AI Bilderstellung Nachdem der Mistkäfer Willi nun bereits so viele Sortierverfahren ausprobiert hat, ist er fix und fertig. Er ist nicht mehr imstande so viele unsortierte Mistkugeln in einem Rutsch abzuarbeiten. Daher überlegt er sich, dass es doch viel schöner wäre, wenn man das Problem vereinfachen könnte. "Ich möchte nicht direkt 5 Kugeln sortieren, sondern lieber 3 und 2 Kugeln separat voneinander. Danach kann ich diese zwei sortierten Teile immer noch wieder zusammenfügen." Und selbst diese 3 Kugeln sind Willi noch zu viel. Er unterteilt auch die 3 Kugeln wieder in 2 Kugeln und 1 Kugel, usw.

Irgendwann ist alles so weit unterteilt, dass Willi jeweils nur noch eine einzelne Mistkugel vor sich sieht. Dabei stellt er fest: "Das ist ja easy: die ist ja bereits sortiert!"

"Wenn ich nun jeweils zwei benachbarte und bereits sortierte Mistkugel-Bereiche wieder zusammenfüge, dann ist das ganz einfach, diese in die korrekte Ordnung zu bringen, denn die jeweils kleinste Zahl ist ganz vorne." Willi muss also nur jeweils die kleinste (=vorderste) Zahl aus den beiden benachbarten Bereichen vergleichen, die kleinere Zahl auswählen und in den neuen sortierten Bereich einfügen.

Schritt für Schritt

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…
Das hinterste Teilarray hat noch immer die Länge 2. Daher muss es nochmals halbiert werden. Damit ist das Ende der Split-Phase erreicht.
Merge-Phase (Verschmelzungsphase): Wir wissen nun, dass alle Teilarrays der Länge 1 jeweils offensichtlich sortiert sind. Nun fügen wir jeweils benachbarte Teilarrays in der korrekten Reihenfolge wieder zusammen. Dabei sollte die Reihenfolge beachtet werden, in der die Arrays zuvor aufgesplittet wurden.
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, um festzustellen, welche Zahl als nächste ausgewählt wird.