Vorlesung Informatik 2 - Teil B: Theorie
2.6 MergeSort
Dieser Algorithmus wurde schon 1945 durch John von Neumann eingeführt und er bringt die Komplexität auf eine weitere Stufe: O(N log N). Er ist ein typischer Vertreter der Divide and Conquer Algorithmen, welche von einem Schritt zum nächsten die Datenmenge um einen Faktor (hier 2) reduzieren.
Es ist ein stabiles Sortierverfahren, allerdings ist er nicht in-situ, er braucht den doppelten Speicherplatz. Allerdings gibt es eine Variante, die mit vier sequentiellen Datenströmen arbeitet, z.B. mit Magnetbändern.
Wir sortieren als Beispiel mal nicht Zahlen, sondern die Buchstaben des Wortes
MAGENBROT. In jedem Schritt unterteilen wir die Daten in jeweils wieder in zwei Hälften, bis nur noch die einzelnen
Buchstaben übrig sind:
MAGENBROT
/ \
/ \
MAGE NBROT
/ \ / \
MA GE NB ROT
/ \ / \ / \ / \
M A G E N B R OT
/ \
O T
---------------------------------
AM EG BN ORT Beim Zusammenfügen werden je zwei Sequenzen
\ / \ /
AEGM BNORT in der richtigen Reihenfolge verschmolzen (merge)
\ /
ABEGMNORT (Reißverschluß)
Wie die meisten Divide-and-Conquer Algorithmen lässt sich Merge-Sort sehr gut rekursiv implementieren. Die Tiefe der Rekursion ist dabei auf O(log N) beschränkt.
Zusammenfassung:
ex situ, stabil, Komplexität O(N log N)
In den Beispielen finden Sie die Klasse MergeSort, welche den Algorithmus implementiert - schauen Sie ihn sich bei Interesse an. In den Übungen integrieren Sie diese Klasse in Aufgabe 11 und können das Laufzeitverhalten ausprobieren.
Ein Teil der sort-Methoden in der Java Klasse Arrays verwendet eine 1993 veröffentlichte Variante des Merge-Sort Algorithmus.