Mergesort

Beispiel, wie Mergesort eine Liste sortiert. Die Listenelemente werden durch Punkte dargestellt. Die waagerechte Achse gibt an, wo sich ein Element in der Liste befindet, die senkrechte Achse gibt an, wie groß ein Element ist.

Mergesort (engl. merge für verschmelzen und sort für sortieren) ist ein stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt.^[1]

Funktionsweise

Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die sortierten kleinen Listen werden dann im Reißverschlussverfahren zu größeren Listen zusammengefügt (engl.: (to) merge), bis wieder eine sortierte Gesamtliste erreicht ist. Das Verfahren arbeitet bei Arrays in der Regel nicht in-place, es sind dafür aber (trickreiche) Implementierungen bekannt. Verkettete Listen sind besonders geeignet zur Implementierung von Mergesort, dabei ergibt sich die in-place-Sortierung fast von selbst.

Veranschaulichung der Funktionsweise

Das Bild veranschaulicht die drei wesentlichen Schritte eines Teile-und-herrsche-Verfahrens, wie sie im Rahmen von Mergesort umgesetzt werden. Der Teile-Schritt ist ersichtlich trivial (die Daten werden einfach in zwei Hälften aufgeteilt). Die wesentliche Arbeit wird beim Verschmelzen (merge) geleistet - daher rührt auch der Name des Algorithmus. Bei Quicksort ist hingegen der Teile-Schritt aufwendig und der Merge-Schritt einfacher (nämlich eine Konkatenierung).

Bei der Betrachtung des in der Grafik dargestellten Verfahrens sollte man sich allerdings bewusst machen, dass es sich hier nur um eine von mehreren Rekursionsebenen handelt. So könnte etwa die Sortierfunktion, welche die beiden Teile 1 und 2 sortieren soll, zu dem Ergebnis kommen, dass diese Teile immer noch zu groß für die Sortierung sind. Beide Teile würden dann wiederum aufgeteilt und der Sortierfunktion rekursiv übergeben, so dass eine weitere Rekursionsebene geöffnet wird, welche dieselben Schritte abarbeitet. Im Extremfall (der bei Mergesort sogar der Regelfall ist) wird das Aufteilen so weit fortgesetzt, bis die beiden Teile nur noch aus einzelnen Datenelementen bestehen.

Implementierung

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei liste die zu sortierenden Elemente enthält.

funktion mergesort(liste);
  falls (Größe von liste <= 1) dann antworte liste
  sonst
      halbiere die liste in linkeListe, rechteListe
      linkeListe = mergesort(linkeListe)
      rechteListe = mergesort(rechteListe)
      antworte merge(linkeListe, rechteListe)

funktion merge(linkeListe, rechteListe);
   neueListe
   solange (linkeListe und rechteListe nicht leer)
   |    falls (erstes Element der linkeListe <= erstes Element der rechteListe)
   |    dann füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
   |    sonst füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
   solange_ende
   solange (linkeListe nicht leer)
   |    füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
   solange_ende
   solange (rechteListe nicht leer)
   |    füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
   solange_ende
   antworte neueListe

Beispiel

Im letzten Merge-Schritt ist das Reißverschlussverfahren beim Mischen angedeutet. Blaue Pfeile verdeutlichen den Aufteilungs-Schritt, grüne Pfeile die Misch-Schritte.

Komplexität

Mergesort ist im Gegensatz zu Quicksort stabil, wenn der Merge-Schritt richtig implementiert ist. Seine Komplexität (Worst-, Best- und Average-Case-Verhalten) beträgt in der Landau-Notation ausgedrückt stets $\mathcal{O}(n \cdot \log (n))$. Damit ist Mergesort hinsichtlich der Komplexität dem Quicksort gewissermaßen überlegen, da der Quicksort (ohne besondere Vorkehrungen) ein Worst-Case-Verhalten von $\mathcal{O}(n^2)$ besitzt. Die Wahrscheinlichkeit, dass dieser Fall auftritt, ist jedoch so gering, dass Quicksort in der Praxis bessere Ergebnisse erzielt.

Für die Laufzeit T(n) von Mergesort bei n zu sortierenden Elementen gilt die Rekursionsformel

$T(n)= \underbrace{T(\lfloor \tfrac{n}{2} \rfloor)}_{\text{Aufwand, den einen Teil zu sortieren}} + \underbrace{T(\lceil \tfrac{n}{2} \rceil)}_{\text{Aufwand, den anderen Teil zu sortieren}} + \underbrace{n}_{\text{Aufwand, die beiden Teile zu verschmelzen}}$

mit dem Rekursionsanfang T(1) = 1.

Nach dem Master-Theorem kann die Rekursionformel durch $2 T(\lfloor \tfrac{n}{2} \rfloor) + n$ bzw. $2 T(\lceil \tfrac{n}{2} \rceil) + n$ approximiert werden mit jeweils der Lösung (2. Fall des Mastertheorems, s. dort) $T(n)=\mathcal{O}(n \cdot \log (n))$

Korrektheit und Terminierung

Der Rekursionsabbruch stellt die Terminierung von Mergesort offensichtlich sicher, so dass lediglich noch die Korrektheit gezeigt werden muss. Dies geschieht, indem wir folgende Behauptung beweisen:

Behauptung: In Rekursionstiefe i werden die sortierten Teillisten aus Rekursionstiefe i + 1 korrekt sortiert.

Beweis: Sei o.B.d.A. die (i + 1)-te Rekursion die tiefste. Dann sind die Teillisten offensichtlich sortiert, da sie einelementig sind. Somit ist ein Teil der Behauptung schon mal gesichert. Nun werden diese sortierten Teillisten eine Rekursionsebene nach oben, also in die i-te Rekursion übergeben. Dort werden diese nach Konstruktion der Mischen-Prozedur von Mergesort korrekt sortiert. Somit ist unsere Behauptung erfüllt und die totale Korrektheit von Mergesort bewiesen.

Natural Mergesort

Natural Mergesort (natürliches Mergesort) ist eine Erweiterung von Mergesort, die bereits vorsortierte Teilfolgen, so genannte runs, innerhalb der zu sortierenden Startliste ausnutzt. Die Basis für den Mergevorgang bilden hier nicht die rekursiv oder iterativ gewonnenen Zweiergruppen, sondern die in einem ersten Durchgang zu bestimmenden runs:

Startliste    : 3--4--2--1--7--5--8--9--0--6
Runs bestimmen: 3--4  2  1--7  5--8--9  0--6
Merge         : 2--3--4  1--5--7--8--9  0--6
Merge         : 1--2--3--4--5--7--8--9  0--6
Merge         : 0--1--2--3--4--5--6--7--8--9

Diese Variante hat den Vorteil, dass sortierte Folgen „erkannt“ werden und die Komplexität im Best-Case $\mathcal{O}(n)$ beträgt. Average- und Worst-Case-Verhalten ändern sich hingegen nicht.

Außerdem eignet sich Mergesort gut für größere Datenmengen, die nicht mehr im Hauptspeicher gehalten werden können - es müssen jeweils nur beim Mischen in jeder Ebene zwei Listen vom externen Zwischenspeicher (z.B. Festplatte) gelesen und eine dorthin geschrieben werden. Eine Variante nutzt den verfügbaren Hauptspeicher besser aus (und minimiert Schreib-/Lesezugriffe auf der Festplatte), indem mehr als nur zwei Teil-Listen gleichzeitig vereinigt werden, und damit die Rekursionstiefe abnimmt.

Sonstiges

Da Mergesort die Startliste sowie alle Zwischenlisten sequenziell abarbeitet, eignet er sich besonders zur Sortierung von verketteten Listen. Für Arrays ist ein temporäres Array derselben Länge des zu sortierenden Arrays als Zwischenspeicher nötig (somit arbeitet Mergesort nicht in-place, s.o.). Quicksort dagegen benötigt kein temporäres Array. Die SGI-Implementierung der Standard Template Library (STL) verwendet den Mergesort als Algorithmus zur stabilen Sortierung ^[2].

Literatur

• Robert Sedgewick: Algorithmen. Pearson Studium, Februar 2002, ISBN 3827370329

Weblinks

• Visualisierung und Tutorial für Mergesort, mit Darstellung der Rekursion
• Demonstration des Merge-Vorgangs (Java-Applet)

Einzelnachweise

1. ↑ Donald E. Knuth: The Art of Computer Programming. Volume 3: Sorting and Searching.. 2 Auflage. Addison-Wesley, 1998, S. 158.
2. ↑ http://www.sgi.com/tech/stl/stable_sort.html stable_sort