Mergesort

graph TD subgraph divide a[76 70 15 97 29 29 65 50] a --> b[76 70 15 97] & c[29 29 65 50] b --> d[76 70] & e[15 97] c --> f[29 29] & g[65 50] d --> h[76] & i[70] e --> j[15] & k[97] f --> l[29] & m[29] g --> n[65] & o[50] end subgraph conquer h --> p[70 76] i --> p j --> q[15 97] k --> q l --> r[29 29] m --> r n --> s[50 65] o --> s p --> t[15 70 76 97] q --> t r --> u[29 29 50 65] s --> u t --> v[15 29 29 50 65 70 76 97] u --> v end

Der Mergesort-Algorithmus sortiert eine Liste

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

In der Divide-Phase werden überhaupt keine Zahlen betrachtet und keine Vergleiche angestellt. Das geschieht erst in der Conquer-Phase. Hier wird die gesamte Liste mehrmals durchlaufen, während die einzelnen Elemente zu sortierten Paaren ge-merge-t werden, die Paare zu Quartetten und so weiter. Jeder dieser Sortierschritte läuft in ${\mathcal {O}}(n)$ und die Anzahl der Durchgänge lässt sich mit $\log(n)$ abschätzen. 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 🇬🇧 🇨🇳 🇮🇩
• Mergesort getanzt 🇬🇧

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort