mini|300px|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 (von ‚verschmelzen‘ und ‚sortieren‘) ist ein stabiler Sortieralgorithmus, der nach dem Prinzip teile und herrsche (divide and conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt.
Funktionsweise Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die kleinen sortierten Listen werden dann im Reißverschlussverfahren zu größeren sortierten Listen zusammengefügt (engl. ), bis eine sortierte Gesamtliste erreicht ist. Das Verfahren arbeitet bei Arrays in der Regel nicht in-place, es sind dafür aber (trickreiche) Implementierungen bekannt, in welchen die Teil-Arrays üblicherweise rekursiv zusammengeführt werden. Verkettete Listen sind besonders geeignet zur Implementierung von Mergesort, dabei ergibt sich die in-place-Sortierung fast von selbst.
Veranschaulichung der Funktionsweise mini|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 und damit automatisch sortiert sind.
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 269px|rechts Im letzten Verschmelzungsschritt ist das Reißverschlussverfahren beim Verschmelzen (in der Abb. „Mischen:“) angedeutet. Blaue Pfeile verdeutlichen den Aufteilungsschritt, grüne Pfeile die Verschmelzungsschritte.
Es folgt ein Beispielcode analog zum obigen Abschnitt „Implementierung“ für den rekursiven Sortieralgorithmus. Er teilt rekursiv absteigend die Eingabe in 2 kleinere Listen, bis diese trivialerweise sortiert sind, und verschmilzt sie auf dem rekursiven Rückweg, wodurch sie sortiert werden. function merge_sort(list x) if length(x) ≤ 1 then return x // Kurzes x ist trivialerweise sortiert. var l := empty list var r := empty list var nx := length(x)−1 // Teile x in die zwei Hälften l und r ... for i := 0 to floor(nx/2) do append x[i] to l for i := floor(nx/2)+1 to nx do append x[i] to r // ... und sortiere beide (einzeln). l := merge_sort(l) r := merge_sort(r) // Verschmilz die sortierten Hälften. return merge(l, r) Beispielcode zum Verschmelzen zweier sortierter Listen. function merge(list l, list r) var y := empty list // Ergebnisliste var nl := length(l)−1 var nr := length(r)−1 var il := 0 for i := 0 to nl+nr+1 do if il > nl then append r[i−il] to y continue if il < i−nr then append l[il] to y il := il+1 continue // Jetzt ist 0 ≤ il ≤ nl und 0 ≤ i−il ≤ nr. if l[il] ≤ r[i−il] then append l[il] to y il := il+1 else append r[i−il] to y return y
Java-Implementation Eine iterative Implementation in der Programmiersprache Java unter Verwendung von verketteten Listen könnte folgendermaßen aussehen:
(Es wird eine merge()-Funktion zum Verschmelzen zweier Listen verwendet, die im Absatz darunter erläutert wird.)void mergeSort(List<Integer> l) { int n = l.size(); //Erstelle n Teillisten. (1 Element pro Liste) (Divide) LinkedList<LinkedList<Integer>> groups = new LinkedList<LinkedList<Integer>>(); for (int i = 0; i < n; i++) { LinkedList<Integer> list = new LinkedList<>(); list.add(l.get(i)); groups.add(list); } //Solange mehrere Gruppen existieren: while (groups.size() > 1) { //Merge die ersten beiden Listen im Vorrat und hänge die verbundene Liste hinten an. groups.addLast(merge(groups.removeFirst(), groups.removeFirst())); } //Überschreibe die unsortierte Liste mit der sortierten Version list = groups.getFirst(); }
Der Merge-Schritt im Detail Gegeben sind zwei in sich sortierte Listen und , die zu einer sortierten Liste zusammengefügt werden sollen.
Man vergleicht nun die beiden kleinsten Elemente (am Anfang der Listen und ), fügt das kleinere zu hinzu und nimmt es aus der jeweiligen Liste oder heraus.
Dies wird so lange wiederholt, bis eine der beiden Listen A oder B leer ist, danach wird der Rest aus der anderen Liste oder (in der noch Einträge vorhanden sind) ans Ende von gehängt.
Der Mergeschritt braucht genau immer Operationen, da jedes Element aus beiden Listen in konstanter Zeit gelöscht und hinzugefügt werden kann. Die Laufzeit beträgt folglich: LinkedList<Integer> merge(LinkedList<Integer> linkeListe, LinkedList<Integer> rechteListe) { LinkedList<Integer> temp = new LinkedList<>(); // Solange noch nicht beide Listen hinzugefügt worden while (!linkeListe.isEmpty() && !rechteListe.isEmpty()) { if (linkeListe.getFirst() <= rechteListe.getFirst()) { temp.addLast(linkeListe.removeFirst()); } else { temp.addLast(rechteListe.removeFirst());
// Füge Rest hinzu, falls etwas übrig ist. temp.addAll(linkeListe); temp.addAll(rechteListe); return temp; }
Komplexität Mergesort ist ein stabiles Sortierverfahren, vorausgesetzt der Merge-Schritt ist entsprechend implementiert. Seine Komplexität beträgt im Worst-, Best- und Average-Case in Landau-Notation ausgedrückt stets .
Damit ist Mergesort hinsichtlich der Komplexität Quicksort grundsätzlich überlegen, da Quicksort (ohne besondere Vorkehrungen) ein von besitzt. Es benötigt jedoch zusätzlichen Speicherplatz (der Größenordnung ), ist also kein In-place-Verfahren.
Für die Laufzeit von Mergesort bei zu sortierenden Elementen gilt die Rekursionsformel
mit dem Rekursionsanfang .
Nach dem Master-Theorem kann die Rekursionsformel durch bzw. approximiert werden mit jeweils der Lösung (2. Fall des Mastertheorems, s. dort) .
Durchschnittliche und maximale Anzahl Vergleiche Sind die Längen der zu verschmelzenden und vorsortierten Folgen dann gilt für die Anzahl der erforderlichen Vergleiche fürs sortierende Verschmelzen , da erstens eine Folge komplett vor der anderen liegen kann, d. h., es ist bzw. oder es ist zweitens (bzw. umgekehrt), sodass die Elemente bis zum letzten Element in jeder Folge verglichen werden müssen. Dabei ist jeweils angenommen, dass das Vergleichen der zwei Folgen bei den Elementen mit niedrigem Index beginnt. Mit
(Subskript für maximal) sei die maximale Anzahl der Vergleiche fürs Verschmelzen bezeichnet. Für die maximale Anzahl an Vergleichen für einen ganzen Mergesort-Lauf von Elementen errechnet sich daraus mit ist die .
Für eine Gleichverteilung lässt sich auch die durchschnittliche Anzahl (Subskript für durchschnittlich) der Vergleiche genau berechnen, und zwar ist für
und für
Dabei ist die Anzahl der Vergleiche für die Anordnung , wobei für das letzte (das am höchsten sortierende) Element in der Folge steht, die (nicht von einem Element aus unterbrochenen) zu gehören und (die auch fehlen können) entweder zu oder zu gehören. Der in den Summenformeln beigegebene Binomialkoeffizient zählt die verschiedenen Möglichkeiten für
Für die durchschnittliche Anzahl an Vergleichen für einen ganzen Mergesort-Lauf von Elementen errechnet man daraus 21,000010,0000032,666730,1111144,666750,0833369,8333110,19444815,733170,158331229,952330,253971645,689490,206942482,059890,2892232121,501290,2345248210,202250,3083964305,053210,2492096514,445450,31838128736,137690,256771921218,912810,323482561726,317930,260613842819,829450,326065123962,640970,262557686405,666570,3273610248947,292170,26352153614345,0148490,32801204819940,0204810,26401307231760,0327690,32833409643974,0450570,26426614469662,0716810,32849819296139,0983050,26438122881,5161E51556490,32857163842,0866E52129930,26444245763,278E53358730,32862327684,5009E54587530,26447491527,0474E57208970,32864655369,6571E59830410,26448983041,5078E615400970,328651310722,0625E620971530,264491966083,2122E632768010,328652621444,3871E644564490,264503932166,8176E669468170,328655242889,2985E694371850,264507864321,4422E7146800650,3286510485761,9646E7199229450,2645015728643,0416E7309329930,3286620971524,1388E7419430410,2645031457286,3978E7650117130,3286641943048,6971E7880803850,2645062914561,3425E81363148810,3286683886081,8233E81845493770,26450125829122,8108E82852126730,32866167772163,8144E83858759690,26450 und findet
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 werden die sortierten Teillisten aus Rekursionstiefe korrekt sortiert.
Beweis: Sei o. B. d. A. die -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 -te Rekursion übergeben. Dort werden diese nach Konstruktion der merge-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 beträgt. Average- und Worst-Case-Verhalten ändern sich hingegen nicht.