Informatikmaterialien
von Tino Hempel

	Richard-Wossidlo-Gymnasium Ribnitz-Damgarten Fachbereich Informatik

Mergesort

Sortierverfahren III – Mergesort

Prinzip des Verfahrens

Das Verfahren wendet das Prinzip "Teile und Herrsche" an, d. h., es findet eine Zerlegung des Problems der Größe n in mehrer Teilprobleme kleinerer Größe statt, die jeweils gelöst und anschließend zu einer Lösung des Grundproblems zusammengesetzt werden.

Der Ablauf erfolgt in 3 Schritten:

Zerlegung der Menge in zwei Hälften

Sortierung der Hälften

Mischen der Hälften zu einer Menge, dabei werden immer die vordersten Elemente der sortierten Hälften verglichen und das jeweils kleinere in die Gesamtmenge getan.

Die Zerlegung wird solange rekursiv fortgesetzt, bis nur noch ein Element der Menge übrig ist.

Beispiel:

Darstellung des Algorithmus als Struktogramm

worst-case-Komplexität

Um zwei Teilfelder zu einem zu verschmelzen, ist 1 Schritt notwendig.
Um vier Teilfelder zu einem zu verschmelzen sind 2 Schritte notwendig.
Um acht Teilfelder zu einem zu verschmelzen sind 3 Schritte notwendig. usw.

Demzufolge existiert ein Zusammenhang zwischen der Schrittzahl und der Anzahl der Teilfelder, nämlich: Teilfeldzahl = 2^Schrittzahl.
Da aber die Schrittzahl gesucht ist, lässt sich die Gleichung umformen zu: Schrittzahl = log₂(Teilfeldzahl).

Also: Zum Zerlegen und zum Verschmelzen benötigt man einen Zeitaufwand von jeweils O(log₂n). Für jedes Verschmelzen ist jeweils ein Vergleichsvorgang erforderlich, der einmal durch das Teilfeld läuft. Sein Zeitaufwand lässt sich also mit O(n) abschätzen.

Somit hat Mergesort einen Zeitaufwand von O(n·log₂n).

Hinweis: In der informatischen Literatur wird häufig die Basis des Logarithmus weggelassen, da sie bezüglich der O-Notation keine spezielle Bedeutung hat. Man spricht meist vom 2er-Logarithmus.

zur Startseite

Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.
Für alle Seiten gilt der

Haftungsausschluss/Disclaimer.