Mergesort einfach erklärt: Ablauf und Laufzeit

Stell dir vor, du sollst viele ungeordnete Zahlen sortieren. Mergesort löst nicht sofort die ganze Aufgabe, sondern zerlegt sie in immer kleinere Aufgaben.

Mergesort arbeitet in drei Schritten:

1. Teilen: Halbiere die Folge ungefähr in eine linke und eine rechte Hälfte.
2. Sortieren: Sortiere beide Hälften auf dieselbe Weise. Folgen mit höchstens einem Element sind bereits sortiert.
3. Verschmelzen: Führe die beiden sortierten Hälften zu einer sortierten Folge zusammen.

Der zweite Schritt ruft dasselbe Verfahren für kleinere Folgen auf. Das nennt man Rekursion. Der Abbruch bei höchstens einem Element verhindert, dass immer weiter geteilt wird.

Beim Merge-Schritt liegen bereits zwei sortierte Folgen vor. Du vergleichst jeweils ihre ersten noch nicht übernommenen Elemente.

So gehst du vor:

1. Vergleiche das nächste Element der linken mit dem nächsten Element der rechten Folge.
2. Übernimm das kleinere Element in die Ergebnisfolge.
3. Rücke nur in der Folge weiter, aus der du das Element genommen hast.
4. Wiederhole den Vergleich, bis eine Folge leer ist.
5. Hänge den unverarbeiteten Rest der anderen Folge an.

Gleiche Schlüssel stabil behandeln

Ein Sortierverfahren heißt stabil, wenn Einträge mit gleichem Sortierschlüssel ihre ursprüngliche Reihenfolge behalten.

Angenommen, 2_A stand vor 2_B. Beim Merge von [2_A, 5] und [2_B, 4] muss bei Gleichheit das linke Element 2_A zuerst übernommen werden. Das Ergebnis beginnt dann mit [2_A, 2_B, ...].

In einer Bedingung wird deshalb links gewählt, wenn links <= rechts gilt. Eine Bedingung mit nur < würde bei Gleichheit rechts wählen und die Stabilität gefährden.

Sortiere nun [7, 2, 6, 3, 8, 1, 5, 4].

Teilen

• [7, 2, 6, 3] und [8, 1, 5, 4]
• [7, 2], [6, 3], [8, 1], [5, 4]
• [7], [2], [6], [3], [8], [1], [5], [4]

Jede entstandene Einzelfolge ist sortiert.

Paarweise verschmelzen

• [7] und [2] werden zu [2, 7].
• [6] und [3] werden zu [3, 6].
• [8] und [1] werden zu [1, 8].
• [5] und [4] werden zu [4, 5].

Danach entstehen größere sortierte Folgen:

• [2, 7] und [3, 6] werden zu [2, 3, 6, 7].
• [1, 8] und [4, 5] werden zu [1, 4, 5, 8].

Im letzten Merge werden diese beiden Folgen zu [1, 2, 3, 4, 5, 6, 7, 8] verbunden.

Für die Korrektheit brauchst du zwei Argumente: Der Merge-Schritt arbeitet korrekt, und die Rekursion erreicht sicher ihre Abbruchbedingung.

Warum der Merge-Schritt stimmt

Während des Verschmelzens gilt folgende Invariante: Die Ergebnisfolge ist sortiert und enthält genau die kleinsten bereits ausgewählten Elemente beider Eingabefolgen.

Das nächste Ergebnis kann nur eines der beiden vordersten unverarbeiteten Elemente sein. Alle späteren Elemente derselben Folge sind mindestens ebenso groß. Wenn du das kleinere der beiden Vorderseiten wählst, bleibt die Ergebnisfolge deshalb sortiert.

Ist eine Eingabefolge leer, kann ihr kein kleineres Element mehr folgen. Der sortierte Rest der anderen Folge darf ohne weitere Schlüsselvergleiche angehängt werden.

Warum die Rekursion stimmt

• Folgen mit höchstens einem Element sind sortiert.
• Jeder rekursive Aufruf arbeitet mit einer kleineren Folge und erreicht daher den Abbruchfall.
• Sind die beiden kleineren Ergebnisse sortiert, erzeugt der korrekte Merge daraus wieder eine sortierte Folge.

So entsteht von den Einzelfolgen bis zur Gesamtfolge auf jeder Ebene ein korrekt sortiertes Ergebnis.

Für $n$ Elemente entstehen ungefähr $\log_2 n$ Teilungsebenen. Bei einer Verdopplung der Eingabe kommt nur eine weitere Ebene hinzu.

Auf jeder Merge-Ebene werden insgesamt alle $n$ Elemente verarbeitet. Lineare Arbeit je Ebene und logarithmisch viele Ebenen ergeben:

$$O(n \log n)$$

Für acht Elemente gibt es drei Teilungsebenen, weil wiederholt 8, 4, 2, 1 Elemente pro Teilfolge auftreten. Im vereinfachten Ebenenmodell ergibt das $8 \cdot 3 = 24$ Verarbeitungseinheiten. Diese Zahl veranschaulicht das Wachstum; sie ist keine gemessene Laufzeit.

Klassischer Mergesort bleibt bei zufälligen, aufsteigend und absteigend angeordneten Eingaben asymptotisch in $O(n \log n)$. Konkrete Laufzeiten und Vergleichszahlen können sich trotzdem unterscheiden.

Beim Merge zweier Folgen mit $a$ und $b$ Elementen sind im schlechtesten Fall höchstens $a+b-1$ Schlüsselvergleiche nötig. Sobald eine Seite leer ist, wird der Rest angehängt.

Zusätzlicher Speicher

Eine übliche Array-Implementierung schreibt Merge-Ergebnisse in ein Hilfsarray. Dafür wird zusätzlicher Speicher der Größenordnung

$$O(n)$$

benötigt. Standard-Mergesort für Arrays arbeitet daher normalerweise nicht in-place, also nicht nur innerhalb des ursprünglichen Arrays mit konstantem Zusatzspeicher.

Die asymptotische Laufzeit ist nicht das einzige Auswahlkriterium. Prüfe auch Stabilität, Speicher, Vorsortierung und die verwendete Datenstruktur.

Natural Mergesort

Runs sind bereits aufsteigend sortierte Abschnitte einer Eingabe. Natural Mergesort erkennt solche Runs und verschmilzt sie, statt die Folge immer künstlich bis zu Einzelelementen zu teilen.

In der Folge [3, 4, 2, 1, 7, 5, 8, 9, 0, 6] sind beispielsweise die Runs [3, 4], [2], [1, 7], [5, 8, 9] und [0, 6] enthalten.

Eine vollständig aufsteigend sortierte Folge bildet nur einen Run. Natural Mergesort kann diesen Fall in $O(n)$ erkennen. Das ändert nichts daran, dass Average und Worst Case weiterhin $O(n \log n)$ betragen.

In-place ist nicht automatisch schneller

Es gibt In-place-Varianten von Mergesort. Eine einfache Variante schafft Platz durch wiederholtes Verschieben von Arrayelementen. Dadurch kann ein Merge im Average und Worst Case bis zu $O(n^2)$ benötigen. Weniger Zusatzspeicher kann also mit deutlich mehr Laufzeit bezahlt werden.

Du beherrschst Mergesort, wenn du den Weg von den Einzelfolgen bis zum Endergebnis erklären, den Merge selbst ausführen und die Wahl des Verfahrens mit Laufzeit, Stabilität und Speicher begründen kannst.