Mergesort

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

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 in der Regel nicht in-place, es sind aber (trickreiche) Verfahren bekannt, die eine Implementierung in-place ermöglichen.

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 die selben 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.

Beispiel

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

Algorithmus in Pseudocode

Ein rekursiver Mergesort in Pascal für ein Feld a[1..N]:

procedure mergesort(links:integer, rechts:integer);
var i,j,k,mid:integer;
    b: array[links..rechts] of datatype;
begin
  if (rechts-links>0) then begin //Abbruchbedingung für Rekursion
    
    // Mittleres Element bestimmen und rekursiver Abstieg
    mid := (rechts+links) div 2; 
    mergesort(links, mid);
    mergesort(mid+1, rechts);
    
    // Mischen der sortierten Unterfelder
    // dabei wird ein Hilfsfeld b verwendet
    //   1. Daten in Hilfsfeld kopieren
    for i:=mid downto links do 
      b[i] := a[i];
    for j:=mid+1 to rechts do 
      b[rechts+mid+1-j] := a[j];
    
    //      Die Felder sind jetzt in b[] so angeordnet, dass sich die
    //      jeweils größten Elemente in der Mitte befinden
    //      i und j zeigen auf auf den linken, bzw. rechten Rand
    //    2. Mischen:
    for k:=links to rechts do
    begin
      if b[i]<b[j] then begin
        a[k]:=b[i];
        i:=i+1;
      end else begin
        a[k]:=b[j];
        j:=j-1;
      end;
    end; // Ende von "for"
  end;   // Ende von "if" (Abbruchbedinung)
end;     // Ende von "procedure"

Wie man in der Abbildung rechts sieht werden die Elemente geschickt im Hilfsfeld b[] angeordnet. Die "Zeiger" i und j wandern von links, bzw. rechts zum Zentrum. Es wird jeweils das kleinere Element eingefügt und der entsprechende Zeiger verschoben, bis alle Elemente eingefügt sind.

In iterativer Version sieht der Algorithmus so aus:

 WHILE (Weitere_Elemente_in_Startliste) {
     Nächste_2er_Liste()
     WHILE (Letzte_2_Listen_gleich_lang) {
         Merge()
     }
 }
 WHILE (Mehr_als_1_Liste) {
     Merge()
 }

Komplexität

Mergesort ist im Gegensatz zu Quicksort stabil. Seine Komplexität beträgt in der Landau-Notation ausgedrückt O(n·log(n)). Damit ist Mergesort hinsichtlich der Komplexität Quicksort überlegen.

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.

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 (nicht in-place). Quicksort dagegen benötigt kein temporäres Array.

Die Variante "natürliches Mergesort" nutzt bereits vorsortierte Teilfolgen, so genannte runs, innerhalb der zu sortierenden Startliste aus. 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

Weitere Sortierverfahren

Siehe auch: Sortierverfahren

Literatur

Robert Sedgewick: Algorithmen. Pearson Studium 2002 ISBN 3827370329

Weblinks