Erklärung:

Mergesort zerteilt das Array rekursiv in möglichst gleich große Teile, bis jedes Teil nur noch ein Element enthält.
Danach werden diese Elemente wieder zusammen gemischt. Daher ähnelt es sehr dem Quicksort-Verfahren.

Nehmen wir hierzu die vorletzte Reihe des folgenden Beispiels. Zuerst wird die 2 mit der 1 verglichen.
Da 1 < 2 wird die 1 in die letzte Zeile geschrieben. Danach wird die 2 mit der 3 verglichen. Da 2 < 3 wird
die 2 in das Array geschrieben usw. Dieser Vorgang wiederholt sich so lange bis kein Element mehr vorhanden ist.

Beispiel:



Aufwand:

Mergesort benötigt bei einem durchschnittlichen Datensatz eine Zeitkomplexität von O(n log n) und ist damit ein optimaler Algorithmus für das Sortierproblem.

>> Allgemeine Fragen oder Probleme mit dem Tutorial? Hier gehts zum Forum!