¶ Merge Sort
Merge Sort ist ein Sortierverfahren, welches über das Spalten und Zusammenfügen von Listen funktioniert.
Die zu sortierende Liste wird immer wieder halbiert, bis Listen mit nur einem Element übrig bleiben. Diese gelten als sortiert.
Anschließend fügt man immer zwei Listen zusammen, indem man jeweils die ersten beiden Elemente vergleicht und das kleinere zuerst der neuen Liste anhängt.
- Da jede so entstehende Liste als sortiert gilt (also das kleinste Element immer am weitesten vorne ist usw.), muss man beim Zusammenfügen der Listen immer nur die momentan ersten Elemente betrachten.
Man fügt die neuen Listen immer zu zweit zusammen, bis nur noch eine Liste übrig bleibt.
Dabei braucht der Algorithmus für jede Liste einer bestimmten Länge immer gleichlang, Worst-, Best- und Average-Case sind also alle gleich.
Man kann den Algorithmus nicht vorzeitig abbrechen
Ablauf von Mergesort als Gif:
Ablauf von Mergesort als Diagramm:
(beides aus der engilschen Wikipedia)
Vorteile: deutlich geringere Sortierzeiten im Vergleich zu einfacheren Verfahren
Nachteile: komplexere Implementierung, mehr Arbeitsspeicher benötigt, für kleinere Datensets langsamer
Vor und Nachteile des Algorithmus erklärt:
https://youcademy.org/merge-sort-pros-cons/#advantages-of-merge-sort