|
Mergesort verfährt nach dem Prinzip
des Divide and Conquer (Teile und Herrsche Prinzip)
Die ursprüngliche Version von
Mergesort teilt eine Folge F rekursiv in gleich große Teilfolgen
auf, um dann die Teilfolgen zu sortieren und dann wieder zusammen zu
mischen.
Hierfür benötigt Mergesort zusätzlichen
externen Speicherplatz, abhängig von der Eingabelänge N. Daher
handelt es sich bei Mergesort um ein externes Sortierverfahren.
Die Methode von MergeSort an
einem Beispiel.
rekursive Sichtweise : für
Graphik hier klicken
Wie
wird gemischt?
Zum Mischen benötigt man ein
Hilfsband. Auf dieses Hilfsband werden nun die Teilfolgen übertragen,
so dass die erste Teilfolge links, die zweite Teilfolge von rechts
in absteigender Reihenfolge übertragen werden:
Nun benötigt man nur noch zwei
Positionszeiger, die jeweils auf die Anfangselemente der Teilfolgen
zeigen. Dann muss man nur noch die jeweiligen Elemente auf die die
Zeiger zeigen vergleichen und dann das kleinere übertragen:
Analyse
:
Für
das Verschmelzen (merge) sind im ungünstigsten Fall höchstens n
Vergleiche und 2n Datenbewegungen (Transport in den Zwischenspeicher
und zurück) erforderlich, also höchstens 3n Dominante Operationen.
Jeder Aufruf von mergesort führt im
Rekursionsfall zu zwei weiteren Aufrufen von mergesort mit halber
Problemgröße.
Da also bei jedem Aufruf von Mergesort
die Reihung halbiert wird, finden insgesamt
log(n) +1 Aufrufe statt. Es verdoppeln
sich auf jeder Stufe die Anzahl derAbschnitte, dafür werden die
Abschnitte aber auch nur halb so groß à
Auf jeder Stufe sind nur halb so viele dominante Operationen nötig.
à
Die Anzahl der Operationen bleibt damit konstant.
à
Mergesort ist in O(3n * (log(n)+1)) à
O(n log(n))
ABER
Mergesort benötigt doppelt so viel Speicherplatz wie ein
In-Place Algorithmus!!!!
FAZIT
-
Worstcase O(n log n)
-
Es baut sich im Gegensatz zu
Quicksort (immer) ein Baum mit logarithmischer Tiefe auf
-
Averagecase O(n log n)
-
Aber zusätzlicher Speicher von Nöten
à
externes Sortieren
-
Eignet sich gut für das Sortieren
von Daten auf Sekundärspeichern
-
Eigentliche Variante ist rekursiv.
-
Es existieren auch iterative
Varianten. à
gleiche Laufzeiten.
-
Iterativ ist Effizienter, da
rekursive Aufrufe auch Speicher belegen
|
