Zum Inhalt springen

Mergesort: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Die Seite wurde neu angelegt: „== Einführung == Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu Quicksort auch stabiler Sortieralgorithmus ist der '''Mergesort''' (von englisch ''merge'' für „verschmelzen“ oder „zusammenführen“). Er wurde 1945 von John von Neumann entwickelt und funktioniert – genau wie Quicksort – nach dem Prinzip '''„Teile und herrsche“''' (''Divide and Conquer''), welches…“
 
Zeile 1: Zeile 1:
== Einführung ==
== Einführung ==
Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu [[Quicksort]] auch [[Sortieren#Stabilität|stabiler]] [[Sortieren|Sortieralgorithmus]] ist der '''Mergesort''' (von englisch ''merge'' für „verschmelzen“ oder „zusammenführen“). Er wurde 1945 von John von Neumann entwickelt und funktioniert – genau wie [[Quicksort]] – nach dem Prinzip '''„Teile und herrsche“''' (''Divide and Conquer''), welches in der Programmierung meist mithilfe von [[Rekursion]] realisiert wird.
Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu [[Quicksort]] auch [[Sortieren#Stabilität|stabiler]] [[Sortieren|Sortieralgorithmus]] ist der '''Mergesort''' (von englisch ''merge'' für „verschmelzen“ oder „zusammenführen“). Er wurde 1945 von John von Neumann entwickelt und funktioniert – genau wie [[Quicksort]] – nach dem Prinzip '''„Teile und herrsche“''' (''Divide and Conquer''), welches in der Programmierung meist mithilfe von [[Rekursion]] realisiert wird.



Version vom 7. November 2026, 13:03 Uhr

Einführung

Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu Quicksort auch stabiler Sortieralgorithmus ist der Mergesort (von englisch merge für „verschmelzen“ oder „zusammenführen“). Er wurde 1945 von John von Neumann entwickelt und funktioniert – genau wie Quicksort – nach dem Prinzip „Teile und herrsche“ (Divide and Conquer), welches in der Programmierung meist mithilfe von Rekursion realisiert wird.

Die Grundidee verfolgt im Vergleich zu Quicksort eine genau umgekehrte Arbeitsverteilung:

  • Quicksort (Hard Split, Easy Join): Steckt die Hauptarbeit in das Aufteilen der Daten anhand eines Pivot-Elements, muss dafür aber am Ende nichts mehr zusammenfügen.
  • Mergesort (Easy Split, Hard Join): Macht sich das Teilen denkbar einfach. Die zu sortierende Liste wird ohne jegliche Vergleiche stur in der Mitte in zwei gleich große Teillisten halbiert („Teile“). Diese Teillisten werden rekursiv so lange weiter halbiert, bis jede Teilliste nur noch aus einem einzigen Element besteht. Da eine Liste mit nur einem Element naturgemäß immer sortiert ist, endet hier die Rekursion. Die eigentliche Sortierarbeit folgt erst beim Rückweg aus der Rekursion: Zwei bereits sortierte Teillisten werden Schritt für Schritt zu einer neuen, größeren sortierten Liste verschmolzen („Herrsche“).

Wie funktioniert das Verschmelzen (Merge-Schritt)?

Sobald zwei benachbarte Teillisten (linke Teilliste und rechte Teilliste) sortiert vorliegen, werden sie nach dem Reißverschlussprinzip zusammengeführt:

  1. Man betrachtet jeweils nur das erste (und damit kleinste) Element der linken Teilliste und das erste Element der rechten Teilliste.
  2. Beide Elemente werden miteinander verglichen.
  3. Das kleinere der beiden Elemente wird aus seiner Teilliste entnommen und hinten an die Ergebnisliste angefügt. (Sind beide Elemente gleich groß, wird das Element der linken Teilliste bevorzugt – dadurch bleibt die relative Reihenfolge gleicher Elemente erhalten und das Verfahren ist stabil).
  4. Dieser Vergleich wird wiederholt, bis eine der beiden Teillisten vollständig geleert ist.
  5. Alle noch übrigen Elemente der anderen Teilliste sind bereits fertig sortiert und größer als alle bisherigen Elemente; sie werden einfach komplett an das Ende der Ergebnisliste angehängt.

Ein wichtiger Unterschied zu Quicksort zeigt sich beim Speicherbedarf: Wird Mergesort auf einem klassischen Array ausgeführt, können die Elemente beim Verschmelzen nicht ohne Weiteres an Ort und Stelle getauscht werden. Es wird ein temporäres Hilfsarray benötigt, weshalb Mergesort auf Arrays nicht In-Place arbeitet. Anders verhält es sich jedoch bei einfach verketteten Listen, für die Mergesort das optimale Sortierverfahren darstellt.

Beispiel

Als Beispiel betrachten wir eine unsortierte Liste mit acht Zahlen. Der Ablauf gliedert sich in zwei Phasen: Zuerst wird die Liste fortlaufend in eine linke Hälfte (blau) und eine rechte Hälfte (rot) geteilt, bis nur noch einzelne Zahlen übrig sind.

1. Teilungsphase (Divide – von oben nach unten):

Ausgangsliste: 7 10 6 4 9 3 1 5

1. Halbierung in der Mitte (je 4 Elemente): 7 10 6 4 | 9 3 1 5

2. Halbierung der Teillisten (je 2 Elemente): 7 10 | 6 4   und   9 3 | 1 5

3. Halbierung bis auf einelementige Listen (Rekursionsbasis erreicht): 7 | 10    6 | 4    9 | 3    1 | 5

2. Verschmelzungsphase (Merge – von unten nach oben):

Nun werden die einelementigen Listen paarweise miteinander verglichen und sortiert zu zweielementigen Listen verschmolzen:

  • Aus 7 und 10 wird 7 10 (da 7 < 10)
  • Aus 6 und 4 wird 4 6 (da 4 < 6)
  • Aus 9 und 3 wird 3 9 (da 3 < 9)
  • Aus 1 und 5 wird 1 5 (da 1 < 5)

Zwischenstand nach der ersten Merge-Ebene: 7 10 | 4 6   und   3 9 | 1 5

Als Nächstes verschmelzen wir die linke Teilliste 7 10 mit der rechten Teilliste 4 6. Wir vergleichen immer nur die vordersten noch nicht verwendeten Elemente (grau = bereits in die Ergebnisliste übernommen):

  1. Vergleich 7 10 mit 4 6 [math]\displaystyle{ \rightarrow }[/math] 4 ist kleiner. Ergebnis bisher: 4
  2. Vergleich 7 10 mit 4 6 [math]\displaystyle{ \rightarrow }[/math] 6 ist kleiner. Ergebnis bisher: 4 6
  3. Die rechte (rote) Teilliste ist nun leer! Der Rest der linken Teilliste (7 10) wird komplett angehängt [math]\displaystyle{ \rightarrow }[/math] 4 6 7 10.

Analog werden auf der rechten Seite 3 9 und 1 5 zu 1 3 5 9 verschmolzen.

Im letzten Schritt werden die beiden sortierten Viererlisten 4 6 7 10 und 1 3 5 9 nach exakt demselben Prinzip zusammengeführt:

  • 4 vs. 1 [math]\displaystyle{ \rightarrow }[/math] 1
  • 4 vs. 3 [math]\displaystyle{ \rightarrow }[/math] 1 3
  • 4 vs. 5 [math]\displaystyle{ \rightarrow }[/math] 1 3 4
  • 6 vs. 5 [math]\displaystyle{ \rightarrow }[/math] 1 3 4 5
  • 6 vs. 9 [math]\displaystyle{ \rightarrow }[/math] 1 3 4 5 6
  • 7 vs. 9 [math]\displaystyle{ \rightarrow }[/math] 1 3 4 5 6 7
  • 10 vs. 9 [math]\displaystyle{ \rightarrow }[/math] 1 3 4 5 6 7 9
  • Rechte Liste leer, Rest (10) anhängen [math]\displaystyle{ \rightarrow }[/math] 1 3 4 5 6 7 9 10

Pseudocode

Der folgende Pseudocode zeigt das Zusammenspiel aus rekursiver Halbierung (mergesort) und dem anschließenden Zusammenführen (verschmelze). links und rechts bezeichnen dabei die Grenzindizes des aktuell betrachteten Bereichs:

funktion mergesort(links, rechts)
    falls links < rechts dann
        // Mittelpunkt berechnen (Ganzzahldivision)
        mitte := (links + rechts) / 2
        
        // Rekursiver Aufruf für die linke Hälfte
        mergesort(links, mitte)
        
        // Rekursiver Aufruf für die rechte Hälfte
        mergesort(mitte + 1, rechts)
        
        // Beide sortierten Hälften zusammenführen
        verschmelze(links, mitte, rechts)
    ende
ende

Warum Mergesort ideal für einfach verkettete Listen ist

Während Quicksort in der Praxis meist das bevorzugte Verfahren für Arrays ist, gilt Mergesort als der optimale Algorithmus zum Sortieren von einfach verketteten Listen (engl. Singly Linked Lists).

In einer einfach verketteten Liste (wie wir sie auch von der Implementierung dynamischer Datenstrukturen wie dem Stapel kennen) sind Elemente nicht hintereinander in einem zusammenhängenden Speicherblock abgelegt, sondern als einzelne Knoten-Objekte (Node). Jeder Knoten kennt lediglich seinen eigenen Inhalt (content) und besitzt eine Referenz (nextNode) auf den unmittelbar nachfolgenden Knoten.

Probleme von Quicksort auf einfach verketteten Listen

  • Kein wahlfreier Zugriff (Random Access): In einem Array kann man in konstanter Zeit [math]\displaystyle{ \mathcal{O}(1) }[/math] auf jedes beliebige Element array[i] (z. B. das mittlere Element für Median-of-Three) zugreifen. In einer einfach verketteten Liste muss man dafür vom Kopfknoten (head) aus Schritt für Schritt durch die Liste wandern, was [math]\displaystyle{ \mathcal{O}(n) }[/math] Zeit kostet.
  • Kein Rückwärtslaufen möglich: Die klassische Partitionierung von Quicksort lässt zwei Zeiger i (von links nach rechts) und j (von rechts nach links) aufeinander zulaufen. Da eine einfach verkettete Liste keine Rückwärtszeiger (prev) besitzt, kann der Zeiger j nicht rückwärts bewegt werden.

Vorteile von Mergesort auf einfach verketteten Listen

  1. Rein sequenzieller Durchlauf (nur Vorwärtszeiger nötig): Beim Verschmelzen zweier Listen werden immer nur die beiden Kopfknoten verglichen und die Referenz auf den nächsten Knoten (nextNode) weitergeschaltet. Der Algorithmus bewegt sich ausschließlich von vorne nach hinten durch die Datenstruktur.
  2. Kein zusätzlicher Speicher für Hilfsarrays nötig ([math]\displaystyle{ \mathcal{O}(1) }[/math] für die Verkettung): Auf einem Array benötigt Mergesort ein Hilfsarray der Größe [math]\displaystyle{ n }[/math], in das die Werte hineinkopiert werden müssen. Bei einer verketteten Liste müssen keine neuen Knoten im Speicher angelegt und keine Daten kopiert werden. Stattdessen werden beim Merge-Schritt einfach die bereits vorhandenen nextNode-Referenzen der Knoten in der richtigen Reihenfolge neu verknüpft („Zeiger umbiegen“). Damit entfällt der größte Nachteil von Mergesort komplett!
  3. Effizientes Finden der Listenmitte (Hasen-und-Igel-Prinzip): Um eine einfach verkettete Liste ohne Kenntnis ihrer Länge in der Mitte zu teilen, nutzt man zwei Zeiger (Fast-and-Slow-Pointer): Der langsame Zeiger (slow) geht pro Schleifendurchlauf einen Knoten weiter, der schnelle Zeiger (fast) springt zwei Knoten weiter. Sobald fast das Ende der Liste erreicht hat, steht slow exakt in der Mitte. Dort wird die Verbindung (slow.nextNode = null) getrennt.
Vergleich: Array vs. Einfach verkettete Liste bei Mergesort
Kriterium Mergesort auf einem Array Mergesort auf einer einfach verketteten Liste
Bestimmen der Mitte Direkt per Indexrechnung [math]\displaystyle{ \mathcal{O}(1) }[/math] Durchlauf per Fast/Slow-Pointer [math]\displaystyle{ \mathcal{O}(n) }[/math]
Zusammenführen (Merge) Werte in ein Hilfsarray kopieren [math]\displaystyle{ \mathcal{O}(n) }[/math] Lediglich nextNode-Zeiger umbiegen [math]\displaystyle{ \mathcal{O}(n) }[/math]
Zusätzlicher Speicher für Elemente [math]\displaystyle{ \mathcal{O}(n) }[/math] (Hilfsarray erforderlich) [math]\displaystyle{ \mathcal{O}(1) }[/math] (keine neuen Knoten nötig)

Java Implementierung

Am besten lassen sich komplexe Algorithmen nachvollziehen, wenn man sie anhand einer Implementierung mit Hilfe eines Debuggers Schritt für Schritt analysiert. Im Folgenden betrachten wir sowohl die klassische Java-Implementierung für ein Array als auch die zeigerbasierte Variante für eine einfach verkettete Liste.

Implementierung für ein Array

In dieser Variante wird ein Array aus Ganzzahlen (int) sortiert. Die Methode merge nutzt ein temporäres Hilfsarray, um die beiden sortierten Teilbereiche [links ... mitte] und [mitte + 1 ... rechts] geordnet zusammenzuführen.

public void mergeSort(int[] array, int links, int rechts) {
    if (links < rechts) {
        // Mitte des aktuellen Bereichs bestimmen
        int mitte = (links + rechts) / 2;

        // Linke und rechte Hälfte rekursiv sortieren
        mergeSort(array, links, mitte);
        mergeSort(array, mitte + 1, rechts);

        // Sortierte Hälften verschmelzen
        merge(array, links, mitte, rechts);
    }
}

public void merge(int[] array, int links, int mitte, int rechts) {
    // Größen der beiden Teillisten berechnen
    int groesseLinks = mitte - links + 1;
    int groesseRechts = rechts - mitte;

    // Temporäre Hilfsarrays anlegen und Daten hineinkopieren
    int[] linkesArray = new int[groesseLinks];
    int[] rechtesArray = new int[groesseRechts];

    for (int i = 0; i < groesseLinks; i++) {
        linkesArray[i] = array[links + i];
    }
    for (int j = 0; j < groesseRechts; j++) {
        rechtesArray[j] = array[mitte + 1 + j];
    }

    // Indizes für linkesArray (i), rechtesArray (j) und das Zielarray (k)
    int i = 0, j = 0;
    int k = links;

    // Reißverschlussverfahren: Jeweils das kleinere Element übernehmen
    while (i < groesseLinks && j < groesseRechts) {
        if (linkesArray[i] <= rechtesArray[j]) {
            array[k] = linkesArray[i];
            i++;
        } else {
            array[k] = rechtesArray[j];
            j++;
        }
        k++;
    }

    // Eventuell verbleibende Restelemente der linken Hälfte anhängen
    while (i < groesseLinks) {
        array[k] = linkesArray[i];
        i++;
        k++;
    }

    // Eventuell verbleibende Restelemente der rechten Hälfte anhängen
    while (j < groesseRechts) {
        array[k] = rechtesArray[j];
        j++;
        k++;
    }
}

Implementierung für eine einfach verkettete Liste

Bei einer einfach verketteten Liste mit einer inneren Klasse Node kommt der Algorithmus vollständig ohne Hilfsarrays aus, da in mergeLists lediglich die nextNode-Verweise der Knoten neu gesetzt werden:

public class LinkedListMergeSort {

    public static class Node {
        int content;
        Node nextNode;

        public Node(int content) {
            this.content = content;
            this.nextNode = null;
        }
    }

    // Sortiert eine einfach verkettete Liste und gibt den neuen Kopfknoten zurück
    public Node mergeSortList(Node head) {
        // Abbruchbedingung: Leere Liste oder Liste mit nur einem Element
        if (head == null || head.nextNode == null) {
            return head;
        }

        // 1. Mitte der Liste über Fast-and-Slow-Pointer bestimmen
        Node mitte = findeMitte(head);
        Node startRechts = mitte.nextNode;

        // Liste in der Mitte auftrennen
        mitte.nextNode = null;

        // 2. Beide Teillisten rekursiv sortieren
        Node linksSortiert = mergeSortList(head);
        Node rechtsSortiert = mergeSortList(startRechts);

        // 3. Sortierte Teillisten durch Umbiegen der Zeiger verschmelzen
        return mergeLists(linksSortiert, rechtsSortiert);
    }

    // Findet den mittleren Knoten mit dem Hasen-und-Igel-Prinzip
    private Node findeMitte(Node head) {
        Node slow = head;
        Node fast = head.nextNode;

        while (fast != null && fast.nextNode != null) {
            slow = slow.nextNode;          // 1 Schritt weiter
            fast = fast.nextNode.nextNode; // 2 Schritte weiter
        }
        return slow;
    }

    // Verschmilzt zwei sortierte Listen ohne neue Knoten zu erzeugen
    private Node mergeLists(Node links, Node rechts) {
        if (links == null) return rechts;
        if (rechts == null) return links;

        // Kleinerer Kopfknoten bildet den Start der verschmolzenen Liste
        if (links.content <= rechts.content) {
            links.nextNode = mergeLists(links.nextNode, rechts);
            return links;
        } else {
            rechts.nextNode = mergeLists(links, rechts.nextNode);
            return rechts;
        }
    }
}

Laufzeitanalyse

Für die Laufzeitanalyse betrachten wir den Rekursionsbaum von Mergesort. Anders als bei Quicksort hängt die Aufteilung der Liste bei Mergesort nicht von den Werten der Elemente oder der Wahl eines Pivot-Elements ab, sondern berechnet sich rein mathematisch aus der Mitte der Indizes: [math]\displaystyle{ \text{mitte} = \lfloor \frac{\text{links} + \text{rechts}}{2} \rfloor }[/math].

Dadurch entstehen in jedem Rekursionsschritt garantiert zwei (nahezu) exakt gleich große Hälften. Der Verzweigungsbaum ist bei Mergesort also in jedem denkbaren Fall vollkommen symmetrisch.

Best-Case, Average-Case und Worst-Case

Wird die Anzahl der zu sortierenden Elemente [math]\displaystyle{ n }[/math] verdoppelt, kommt durch die fortlaufende Halbierung immer genau eine einzige neue Rekursionsebene hinzu. Die Höhe des Rekursionsbaums (Anzahl der Teilungsebenen) beträgt somit immer [math]\displaystyle{ \log_2(n) }[/math]:

Zu sortierende Elemente [math]\displaystyle{ n }[/math] 4 8 16 32
Als Zweierpotenz [math]\displaystyle{ \color{green}{2^2} }[/math] [math]\displaystyle{ \color{green}{2^3} }[/math] [math]\displaystyle{ \color{green}{2^4} }[/math] [math]\displaystyle{ \color{green}{2^5} }[/math]
Anzahl Rekursionsebenen [math]\displaystyle{ \log_2(n) }[/math] 2 3 4 5

Nun bestimmen wir den Aufwand pro Ebene beim Zusammenführen (merge):

  • Auf einer Ebene mit [math]\displaystyle{ k }[/math] Teilproblemen der Größe [math]\displaystyle{ \frac{n}{k} }[/math] wird beim Verschmelzen jedes der insgesamt [math]\displaystyle{ n }[/math] Elemente genau einmal in die Hand genommen, verglichen und an seine neue Position übertragen.
  • Der Arbeitsaufwand auf jeder einzelnen Ebene ist in der Summe über alle Teillisten hinweg also immer linear proportional zu [math]\displaystyle{ n }[/math], das heißt [math]\displaystyle{ \mathcal{O}(n) }[/math].

Multiplizieren wir die Arbeit pro Ebene ([math]\displaystyle{ n }[/math] Operationen) mit der Anzahl der Ebenen ([math]\displaystyle{ \log_2(n) }[/math]), ergibt sich unabhängig von der Vorsortierung der Eingabedaten:

[math]\displaystyle{ T(n) = n \cdot \log_2(n) }[/math]
  • Best-Case (Bester Fall): Selbst wenn die Liste bereits aufsteigend sortiert ist, teilt Mergesort sie bis auf Einzelelemente herunter und prüft beim Verschmelzen die Elemente (pro Merge zweier Listen der Länge [math]\displaystyle{ \frac{m}{2} }[/math] sind im besten Fall [math]\displaystyle{ \frac{m}{2} }[/math] Vergleiche nötig, da eine Hälfte sofort komplett kleiner ist als die andere). Da jedoch auf jeder der [math]\displaystyle{ \log_2(n) }[/math] Ebenen weiterhin alle [math]\displaystyle{ n }[/math] Elemente zusammengeführt werden müssen, liegt die Laufzeit bei [math]\displaystyle{ \mathcal{O}(n \log n) }[/math].
  • Average-Case (Durchschnittlicher Fall): Bei zufällig verteilten Daten beträgt die Laufzeit [math]\displaystyle{ \mathcal{O}(n \log n) }[/math].
  • Worst-Case (Schlechtester Fall): Der ungünstigste Fall für die Anzahl der Vergleiche tritt ein, wenn beim Verschmelzen abwechselnd ein Element aus der linken und ein Element aus der rechten Teilliste gewählt werden muss (z. B. beim Verschmelzen von 1 3 5 7 und 2 4 6 8). Selbst dann sind pro Ebene maximal [math]\displaystyle{ n - 1 }[/math] Vergleiche nötig. Ein Entarten des Baumes zu einer Kette wie bei Quicksort ([math]\displaystyle{ \mathcal{O}(n^2) }[/math]) ist bei Mergesort ausgeschlossen. Die Laufzeit beträgt auch im Worst-Case garantiert [math]\displaystyle{ \mathcal{O}(n \log n) }[/math].

Platzkomplexität (Speicherbedarf)

Bei der Bewertung der Platzkomplexität muss zwischen den beiden Datenstrukturen unterschieden werden:

  • Auf einem Array: Da das Hilfsarray beim Verschmelzen bis zu [math]\displaystyle{ n }[/math] Elemente aufnehmen muss (hinzu kommen [math]\displaystyle{ \mathcal{O}(\log n) }[/math] Speicherrahmen auf dem Aufruf-Stack für die Rekursion), beträgt die Platzkomplexität [math]\displaystyle{ \mathcal{O}(n) }[/math].
  • Auf einer einfach verketteten Liste: Da lediglich Zeiger umgebogen und keine neuen Knoten erzeugt werden, wird nur der Speicherplatz für die [math]\displaystyle{ \log_2(n) }[/math] geschachtelten Rekursionsaufrufe auf dem Call-Stack benötigt. Die Platzkomplexität sinkt dadurch auf [math]\displaystyle{ \mathcal{O}(\log n) }[/math] (bzw. bei einer iterativen Bottom-Up-Implementierung sogar auf [math]\displaystyle{ \mathcal{O}(1) }[/math]).

Direkter Vergleich: Mergesort vs. Quicksort

Eigenschaft Mergesort Quicksort
Best-Case Zeitkomplexität [math]\displaystyle{ \mathcal{O}(n \log n) }[/math] [math]\displaystyle{ \mathcal{O}(n \log n) }[/math]
Average-Case Zeitkomplexität [math]\displaystyle{ \mathcal{O}(n \log n) }[/math] [math]\displaystyle{ \mathcal{O}(n \log n) }[/math]
Worst-Case Zeitkomplexität [math]\displaystyle{ \mathcal{O}(n \log n) }[/math] [math]\displaystyle{ \mathcal{O}(n^2) }[/math]
Platzkomplexität (auf Array) [math]\displaystyle{ \mathcal{O}(n) }[/math] (nicht In-Place) [math]\displaystyle{ \mathcal{O}(\log n) }[/math] (In-Place)
Stabilität Ja (stabil) Nein (in der Regel instabil)
Optimale Datenstruktur Einfach verkettete Listen Arrays