Page in English
Mergesort
Mergesort ist ein sehr effizientes Sortierverfahren, das nach
dem "divide and conquer"-Prinzip arbeitet und daher stark auf
Rekursion basiert.
Legende:
rosa: größerer Vergleichspartner
rot: kleinerer Vergleichspartner
gelb: temporäres Array
orange: teilsortiertes Array
blau: Animation aktiv
Die Idee ist wie folgt:
- Falls die Reihung weniger als zwei Elemente enthält, sind
wir bereits fertig.
- Ansonsten wird die Reihung immer wieder rekursiv in zwei gleich
große Hälften aufgespalten, bis Reihungen der Größe 1 erreicht
sind;
- Dann werden je zwei bereits sortierte Teilreihen zu einer
groesseren sortierten Teilreihung zusammengeführt ("merged").
Das Vorgehen beim "merging" erschließt sich am einfachsten am
Beispiel:
-
arr = 2,3,5,4,6 besteht aus den bereits sortierten
Teilreihungen
arr1 = 2,3,5 und arr2 = 4,6. -
ein temporäres Array der Länge 5 wird wie folgt
belegt:
temp = 2,3,5,6,4 - also arr1, gefolgt von arr2 von hinten herein gelesen.
- Dann geht man von vorne und hinten simultan durch das
temporäre array, und schreibt die Werte nach groesse geordnet
in arr hinein:
-
2 <= 4, damit arr [0] = 2; gehe von vorne her eins nach rechts.
("i++")
-
3 <= 4, damit arr [1] = 3; gehe von vorne her eins nach rechts.
("i++")
-
5 > 4, damit arr[2] = 4; gehe von hinten her eins nach links.
("j--")
-
5 <= 6, damit arr[3] = 5; gehe von vorne her eins nach rechts.
("i++")
-
und zuletzt wird noch die übrige 6 untergebracht:
6 <= 6, damit arr[4] = 6; gehe von vorne her eins nach rechts.
("i++")
Nun haben sich die Indizes gekreuzt ( j<i ), und wir sind
fertig.
Die Laufzeit lässt sich wie folgt bestimmen: Gerade haben
wir gesehen, das für das "Merging" einer Reihung der
Länge n genau n Vergleiche benötigt werden. Nun kann man
eine Rekursionsgleichung fuer die Anzahl der Vergleiche aufstellen,
die etwa so aussieht:
V(n) = 2 V(n/2) + n
Denn zum Sortieren eines Feldes der Länge n muss man erst
zwei Felder (ungefähr) der halben Länge sortieren, und
dann die beiden Felder mischen, was n Vergleiche kostet. Die
Lösung dieser Rekursionsgeleichung führt - im besten wie
auch im schlechtesten Fall auf eine Laufzeit von O(n log n).
Literatur:
Eine exakte Laufzeitanalyse findet sich beispielsweise in:
"Steger, Angelika: Diskrete Strukturen. Band 1; Kap.4.1.1"
Links zu Mergesort:
zurück zur Startseite
