Quelltext der Seite Mergesort

{{Thumbnailbox|INHALT={{#invoke:Mergesort|example}}
|CAPTION=Der Mergesort-Algorithmus sortiert eine Liste}}
[[Mergesort]] ist ein [[Algorithmus|Sortieralgorithmus]], der nach dem Prinzip ''[[Divide and Conquer]]'' arbeitet; und zwar wie folgt:

Gegeben: Liste <code>A</code> der Länge <code>n</code>.

# Falls <code>n < 2</code>:<code>A</code> ist sortiert, gib <code>A</code> zurück.
# 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.

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 {{O|n}} und die Anzahl der Durchgänge lässt sich mit <math>\log(n)</math> abschätzen. Anders als bei [[Quicksort]], das im schlimmsten Fall <math>n</math> Mal unterteilt werden muss, muss die Liste bei Mergesort genau <math>\log n</math> Mal unterteilt werden. Es ergibt sich eine [[Laufzeit|Gesamtlaufzeit]] in {{O|n\log n}}.

{{Navigationsleiste Sortieralgorithmen|LINKS=* [https://www.youtube.com/watch?v=dENca26N6V4 Mergesort getanzt] {{Flagge|GB}}}}