Mergesort

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

Gegeben: Liste A der Länge n.

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

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