Mergesort

Grundprinzip und Funktionsweise

Mergesort ist ein stabiler Sortieralgorithmus nach dem Prinzip „Teile und herrsche“ (divide and conquer). Stabil bedeutet hier: Beim Verschmelzen wird bei gleichen Elementen zuerst das Element aus der linken Liste übernommen, sodass ihre Reihenfolge erhalten bleibt.

Die zu sortierende Liste wird wiederholt in zwei kleinere Listen geteilt. Dieser Vorgang wird fortgesetzt, bis nur noch Listen mit höchstens einem Element vorliegen; diese gelten automatisch als sortiert. Anschließend werden die sortierten Teillisten schrittweise zu größeren sortierten Listen verschmolzen (merge), bis die vollständige Liste sortiert ist.

Beim Merge-Schritt werden jeweils die ersten, also kleinsten noch nicht übernommenen Elemente zweier sortierter Listen verglichen. Das kleinere Element wird in die Ergebnisliste eingefügt und aus seiner Ursprungsliste entfernt. Ist eine der beiden Listen leer, wird der Rest der anderen Liste unverändert angehängt. Die wesentliche Arbeit des Algorithmus liegt in diesem Verschmelzen; bei Quicksort ist dagegen vor allem das Aufteilen aufwendig.

Bei Arrays arbeitet Mergesort normalerweise nicht in-place, benötigt also zusätzlichen Speicher. Für verkettete Listen ist das Verfahren besonders geeignet, weil sich die Listen dort nahezu ohne zusätzlichen Speicher zusammenführen lassen.

Implementierung und Beispiel

Der rekursive Ablauf lässt sich so zusammenfassen:

• Falls die Größe der Liste höchstens 1 ist, wird sie unverändert zurückgegeben.
• Andernfalls wird die Liste in eine linke und eine rechte Hälfte geteilt.
• Beide Hälften werden rekursiv sortiert.
• Die beiden sortierten Hälften werden mit merge zu einer sortierten Liste verbunden.

Der Merge-Schritt benötigt bei zwei Listen A und B genau |A| + |B| Operationen, weil jedes Element einmal gelöscht und in konstanter Zeit in die Ergebnisliste eingefügt wird. Seine Laufzeit beträgt daher O(|A| + |B|).

Ein Beispiel des Artikels für Natural Mergesort beginnt mit der Liste 3--4--2--1--7--5--8--9--0--6. Zunächst werden bereits aufsteigend sortierte Teilfolgen, sogenannte runs, erkannt: 3--4, 2, 1--7, 5--8--9 und 0--6. Danach werden diese Folgen schrittweise verschmolzen:

• 2--3--4, 1--5--7--8--9, 0--6
• 1--2--3--4--5--7--8--9, 0--6
• 0--1--2--3--4--5--6--7--8--9

Eine iterative Java-Implementation mit verketteten Listen kann zunächst aus jedem Element eine ein-elementige Teilliste erzeugen. Solange mehr als eine Teilliste vorhanden ist, werden die ersten beiden Listen verschmolzen und die Ergebnisliste hinten eingereiht. Am Ende bleibt eine sortierte Liste übrig.

Komplexität, Vergleiche und Korrektheit

Für n Elemente besitzt Mergesort im Worst-Case, Best-Case und Average-Case stets die Laufzeit O(n · log(n)). Die Rekursionsformel lautet

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + O(n), mit T(1) = 1.

Nach dem Master-Theorem kann sie durch 2 T(⌊n/2⌋) + n beziehungsweise 2 T(⌈n/2⌉) + n angenähert werden; beide Formen führen zu T(n) = O(n · log(n)). Quicksort besitzt ohne besondere Vorkehrungen im Worst-Case Θ(n²), während Mergesort diese Laufzeitgrenze nicht hat. Dafür benötigt Mergesort zusätzlichen Speicher der Größenordnung O(n) und ist normalerweise kein In-place-Verfahren. Für ein temporäres Array reicht die halbe Elementanzahl n/2; unoptimierte Implementierungen verwenden teilweise ein Array der Größe n.

Beim Verschmelzen zweier vorsortierter Folgen mit Längen l₀ und l₁ liegt die Zahl M der Vergleiche zwischen

min(l₀, l₁) ≤ M ≤ l₀ + l₁ − 1.

Die maximale Zahl der Vergleiche für einen vollständigen Lauf mit n Elementen ist

Sₘ(n) = n l − 2ˡ + 1, mit l := ⌈log₂(n)⌉.

Bei Gleichverteilung gilt für gleich lange Folgen l₁ = l₀ die durchschnittliche Zahl V∅(l₀,l₀) = 2 l₀²/(l₀+1),

und für l₁ = l₀ − 1 gilt V∅(l₀,l₀−1) = 2 l₀²/(l₀+1) − 1.

Für einen vollständigen Lauf gilt die Schranke Sₘ(n) − 0,3286560975 · n ≤ S∅(n) ≤ Sₘ(n).

Die Terminierung folgt aus dem Rekursionsabbruch bei Listen mit höchstens einem Element. Die Korrektheit wird von unten nach oben gezeigt: Einelementige Listen sind sortiert; der Merge-Schritt erzeugt aus zwei sortierten Teillisten wieder eine korrekt sortierte Liste. Dadurch sind schließlich alle Rekursionsebenen und die Gesamtliste korrekt sortiert.

Natural Mergesort und externe Daten

Natural Mergesort nutzt bereits vorsortierte Teilfolgen, die sogenannten runs, in der Startliste. Statt zunächst ausschließlich rekursiv oder iterativ gebildete Zweiergruppen zu verwenden, werden die runs in einem ersten Durchgang bestimmt und anschließend zusammengeführt.

Der Vorteil besteht darin, dass vorhandene Ordnung erkannt wird. Im Best-Case beträgt die Komplexität O(n). Average-Case und Worst-Case bleiben unverändert.

Mergesort eignet sich außerdem für große Datenmengen, die nicht vollständig im Hauptspeicher Platz finden. Auf jeder Verschmelzungsebene müssen jeweils zwei Listen aus einem externen Zwischenspeicher, etwa einer Festplatte, gelesen und eine Ergebnisliste dorthin geschrieben werden. Durch das gleichzeitige Vereinigen von mehr als zwei Teillisten kann die Rekursionstiefe sinken; dadurch lässt sich der Hauptspeicher besser nutzen und die Zahl der Festplattenzugriffe verringern.

Paralleler Mehrwege-Mergesort

Mergesort lässt sich wegen seines Teile-und-herrsche-Prinzips parallel ausführen. Beim einfachen parallelen Mergesort werden die beiden rekursiven Sortieraufrufe gleichzeitig gestartet und anschließend zusammengeführt. Der Spann beträgt jedoch Θ(n); gegenüber der sequentiellen Version ergibt sich dadurch nur eine Verbesserung um den Faktor Θ(log n), weil die sequentielle Mischmethode den Flaschenhals bildet.

Eine parallele Mischmethode wählt in der längeren sortierten Folge ein mittleres Element. Durch binäre Suche wird seine Position in der anderen Folge bestimmt. Damit kann seine endgültige Position in der Ergebnisfolge berechnet werden. Die kleineren und größeren Teilfolgen werden anschließend rekursiv parallel gemischt. Für die Sortierung gilt

T∞sort(n) = T∞sort(n/2) + T∞merge(n) = T∞sort(n/2) + Θ(log(n)²),

mit der Lösung T∞sort = Θ(log(n)³). Die Parallelisierbarkeit beträgt Θ(n/(log n)²).

Der parallele Mehrwege-Mergesort verallgemeinert das binäre Mischen auf k sortierte Folgen und eignet sich für p Prozessoren. Jeder Prozessor sortiert zunächst lokal n/p Elemente. Danach werden globale Trennelemente mit Rang j n/p bestimmt, die lokalen Folgen in Teilfolgen aufgeteilt und die passenden Teilfolgen auf die Prozessoren verteilt. Jeder Prozessor führt anschließend ein p-Wege-Mischen aus. Die Trennelemente sorgen für perfekte Lastverteilung: Jeder Prozessor erhält n/p Elemente, und alle Elemente des Prozessors i sind kleiner oder gleich den Elementen des Prozessors i+1.

Die Methode msSelect bestimmt ein Trennelement mithilfe zufällig gewählter Pivot-Elemente und binärer Suche. Ihre erwartete Laufzeit beträgt O(p log(n/p) log(n)). Für den vollständigen parallelen Mehrwege-Mergesort ergibt sich

O((n/p) log(n/p) + p log(n/p) log(n) + (n/p) log(p)).

Das Verfahren ist für große Datenmengen und Computer-Cluster skalierbar. In realen Systemen müssen jedoch zusätzlich Speicherhierarchie und Kommunikationsaufwand zwischen Prozessoren berücksichtigt werden. Eine mehrstufige Variante teilt p Prozessoren in r Gruppen der Größe p' und wiederholt die Aufteilung rekursiv innerhalb dieser Gruppen, um Kommunikation und viele kleine Nachrichten zu reduzieren.