Page in English 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:
  1. Falls die Reihung weniger als zwei Elemente enthält, sind wir bereits fertig.
  2. Ansonsten wird die Reihung immer wieder rekursiv in zwei gleich große Hälften aufgespalten, bis Reihungen der Größe 1 erreicht sind;
  3. 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:

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

Valid XHTML 1.0!