Mergesort

Mergesort/Beispiel

Der Mergesort-Algorithmus sortiert die Liste [94, 73, 58, 61, 22, 20, 46, 75]

Mergesort ist ein Sortieralgorithmus, der nach dem Prinzip Divide and Conquer arbeitet; und zwar wie folgt:

Gegeben: Liste A der Länge n.

1. Falls n < 2:A ist sortiert, gib A zurück.
2. Ansonsten: Teile die Liste in zwei möglichst gleich große Hälften
3. Sortiere die beiden Hälften mit Mergesort
4. Füge die sortierten Teillisten nach folgendem Verfahren zusammen:
   1. Betrachte das erste Element der beiden Teillisten
   2. Wähle das kleinere davon aus, entferne es aus der Teilliste und füge es in die sortierte Gesamtliste ein
   3. Wiederhole diese beiden Schritte für den Rest der beiden Teillisten, bis beide leer sind.

Die Schritte 1 bis 3 bilden die Divide-Phase, Schritt 4 die Conquer-Phase des Algorithmus.

Laufzeit

Um die Liste in zwei Haufen zu unterteilen, muss man alle n Elemente betrachten, ist also in ${\mathcal {O}}(n)$. Das Zusammenfügen am Ende hat eine Laufzeit, die nicht von der Länge der Eingabeliste abhängt, ist also in ${\mathcal {O}}(1)$. Anders als bei Quicksort, das im schlimmsten Fall n Mal unterteilt werden muss, muss die Liste bei Mergesort genau $\log n$ Mal unterteilt werden. Es ergibt sich eine Gesamtlaufzeit in ${\mathcal {O}}(n\log n)$.

Weblinks

• Sortieralgorithmen auf VisuAlgo.net 🇬🇧 🇨🇳 🇮🇩

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort