Natural Mergesort

Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt.

Der zusätzliche Platzverbrauch des Mergesort-Algorithmus schwankt implementierungsabhängig. Der Algorithmus ist jedoch auf Arrays im Allgemeinen nicht in-place.

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
       antworte merge(mergesort(linkeListe), mergesort(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 geeignet implementiert wird. Seine Komplexität (Worst-, Best- und Average-Case-Verhalten) beträgt in der Landau-Notation ausgedrückt stets $\mathcal{O}(n \log(n))$. Damit ist Mergesort hinsichtlich der Komplexität Quicksort gewissermaßen überlegen, da Quicksort ein Worst-Case-Verhalten von $\mathcal{O}(n^2)$ besitzt. Allerdings ist bei Quicksort bei vorherigem zufälligem Mischen die Wahrscheinlichkeit, dass dieser Fall auftritt, so gering, dass Quicksort in der Praxis bessere Ergebnisse erzielt.

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.

Literatur

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

Weblinks

• Erklärung auf Linux-Related.de, mit Bottom-Up-Mergesort
• Visualisierung und Tutorial für MergeSort, mit Darstellung der Rekursion
• Java-Applet zur Demonstration
• Weiteres Java-Applet