Mergesort einfach erklärt: Ablauf und Laufzeit

Mergesort sortiert eine Liste, indem er sie in kleinere Listen zerlegt. Jede kleine Liste wird für sich sortiert. Danach werden die sortierten Listen im Reißverschlussverfahren zu größeren sortierten Listen zusammengefügt, bis die ganze Liste sortiert ist. Die genaue Regel dafür lernst du im nächsten Abschnitt.

Der Teile-Schritt ist einfach: Die Liste wird in zwei Hälften geteilt. Das geht rekursiv weiter. Rekursiv heißt: Das Verfahren ruft sich für die kleineren Teile selbst wieder auf. Das Teilen endet erst, wenn die Teile nur noch aus einzelnen Elementen bestehen. Ein einzelnes Element ist automatisch sortiert.

Die eigentliche Arbeit leistet das Verschmelzen (englisch merge). Daher hat der Algorithmus seinen Namen. Im Pseudocode, einer vereinfachten Programmschreibweise, gibt mergesort eine Liste mit höchstens einem Element unverändert zurück. Sonst halbiert er die Liste, sortiert beide Hälften mit mergesort und verschmilzt die Ergebnisse mit merge. Die Zerlegung läuft rekursiv abwärts, das Verschmelzen geschieht auf dem Rückweg.

Achtung bei der Reihenfolge: Das Beispiel unten ist Ebene für Ebene aufgeschrieben. Das Programm erledigt dagegen erst die linke Hälfte vollständig und dann die rechte.

Beim Verschmelzen sind zwei in sich sortierte Listen A und B gegeben. Daraus entsteht eine sortierte Ergebnisliste C.

So geht es: Du vergleichst die beiden kleinsten Elemente, das sind die am Anfang der Listen. Das kleinere fügst du zu C hinzu und nimmst es aus seiner Liste heraus. Das wiederholst du, bis eine der beiden Listen leer ist. Dann hängst du den Rest der anderen Liste ans Ende von C.

Sind die beiden Anfangselemente gleich, entscheidet die Regel. Mit „kleiner oder gleich“ kommt bei Gleichheit das Element aus der linken Liste A zuerst. So bleibt die Reihenfolge gleicher Schlüssel erhalten. Der Schlüssel ist der Wert, nach dem sortiert wird. Mergesort ist stabil, vorausgesetzt der Merge-Schritt ist entsprechend implementiert.

Stabilität fällt nur auf, wenn Datensätze mit gleichem Schlüssel unterscheidbar sind, zum Beispiel Zahl plus Name. Sind sie in keiner Weise unterscheidbar, verhalten sich stabile und instabile Verfahren gleich. Wichtig wird Stabilität, wenn mehrere Sortierläufe nacheinander einen kombinierten Schlüssel ergeben sollen: Der zweite Lauf muss die Ordnung des ersten erhalten.

Die Laufzeit misst man mit Landau-Symbolen wie O(n·log n). Sie geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten an, und zwar abhängig von der Größe n des Problems. Für Mergesort gilt im Worst-Case (schlechtester Fall), im Best-Case (bester Fall) und im Average-Case (durchschnittlicher Fall) stets O(n·log n).

Dazu brauchst du zwei Dinge. Erstens: Ein Merge-Schritt braucht genau |A|+|B| Operationen, weil jedes Element in konstanter Zeit gelöscht und hinzugefügt werden kann. Zweitens: Du zählst die Ebenen.

Im Beispiel mit 8 Zahlen gibt es 3 Teilungsschritte: 8 wird zu 4 und 4, dann zu 2 und 2 und 2 und 2, dann zu 8 Einzelzahlen. Also gibt es 3 Ebenen, auf denen verschmolzen wird. Auf jeder dieser Ebenen wird jede der 8 Zahlen einmal eingefügt, wie die Tabelle zeigt.

Der Logarithmus zur Basis 2 passt dazu: log₂ 8 = 3. Im Beispiel gilt also n = 8 Zahlen pro Ebene und log₂ 8 = 3 Ebenen. Das passt zu n·log n. Wir zeigen das aber nur an diesem Beispiel. Es ist kein allgemeiner Beweis für jede Listengröße.

Mergesort braucht zusätzlichen Speicherplatz der Größenordnung O(n). Er ist deshalb kein In-place-Verfahren. In-place heißt: Es wird kaum zusätzlicher Speicher gebraucht. Bei Arrays arbeitet er in der Regel nicht in-place. Für Arrays wird normalerweise ein temporäres Array derselben Länge als Zwischenspeicher verwendet. Bei optimierter Implementierung reicht die halbe Größe (n/2). Quicksort braucht dagegen kein temporäres Array.

Verkettete Listen sind besonders geeignet für Mergesort. Dabei ergibt sich die in-place-Sortierung fast von selbst. Auch für große Datenmengen, die nicht mehr in den Hauptspeicher passen, eignet sich Mergesort gut: Beim Verschmelzen müssen in jeder Ebene nur zwei Listen vom externen Zwischenspeicher (zum Beispiel Festplatte) gelesen und eine dorthin geschrieben werden.

Beim Worst-Case ist Mergesort hinsichtlich der Komplexität Quicksort überlegen: Mergesort braucht stets O(n·log n), Quicksort ohne besondere Vorkehrungen im Worst-Case Θ(n²). Eine Variante, Natural Mergesort, nutzt bereits vorsortierte Teilfolgen (runs) der Startliste. Ihre Komplexität im Best-Case beträgt O(n). Average- und Worst-Case ändern sich nicht.

Brauchst du stabiles Sortieren, ist Mergesort eine gute Wahl. Quicksort ist ein Beispiel für ein instabiles Verfahren. Wer damit sortiert und die Reihenfolge gleicher Schlüssel behalten will, kann etwa eine Reihenfolgenummer ergänzen. Weniger aufwändig ist es, gleich ein stabiles Verfahren zu benutzen.