Einführung in den Merge-Sort Algorithmus

Merge-Sort-Algorithmus

Hier handelt es sich um einen der komplexeren Algorithmen. Mergesort gehört zur Klasse der "divide and conquer" Algorithmen. Um die Liste zu sortieren wird sie so oft halbiert bis nur noch einzelne Elemente übrig sind. Im Anschluss wird dann die Liste "gemerged". Das bedeutet, dass die vielen einzelnen "Listen", die wir hier nun haben, wieder zusammengesetzt und ihre Elemente an ihre korrekte Position gesetzt werden. Mergesort arbeitet stabil, arbeitet aber out-of-place und gehört damit zu den speicherintensiven Algorithmen. Dafür ist es ein sehr schneller Algorithmus, der auch problemlos mit großen, unsortierten Listen klarkommt. Mergesort funktioniert nach dem "Teile-und-herrsche"-Prinzip („divide and conquer“). Zunächst werden die zu sortierenden Elemente in zwei Hälften geteilt. Die entstandenen Sub-Arrays werden dann wieder geteilt – und wieder, bis Sub-Arrays der Länge 1 entstanden sind:

Nun werden in umgekehrter Richtung jeweils zwei Teil-Arrays so zusammengeführt ("gemerged"), dass jeweils ein sortiertes Array entsteht. Im letzten Schritt werden die zwei Hälften des ursprünglichen Arrays gemerged, so dass dieses letztendlich sortiert ist.

Die Laufzeitkomplexität beim Mergesort ist O(n log n).

Lernvideo zum Mergesort
Lernvideo

Hinweis: Alle Ergebnisse und Zwischenergebnisse müssen in Moodle abgegeben werden.