Zum Inhalt springen

Mergesort: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Keine Bearbeitungszusammenfassung
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''' (Sortieren durch Mischen). Er funktioniert nach dem Prinzip '''„Teile und herrsche“''' (''Divide and Conquer''), bei dem aus einem großen Problem zwei kleinere Teilprobleme gemacht werden, was in der Programmierung mithilfe von [[Rekursion]] umgesetzt wird.


Die Grundidee gliedert sich in zwei Phasen:
* '''Teilen:''' Das zu sortierende Feld wird fortlaufend in der Mitte in zwei Hälften geteilt, bis jedes Teilfeld nur noch aus einer einzigen Zahl besteht. Da eine einzelne Zahl für sich genommen immer sortiert ist, endet hier das Teilen (Abbruch der [[Rekursion]]).
* '''Mischen:''' Anschließend geht der Algorithmus den Weg wieder zurück und mischt jeweils zwei benachbarte, bereits sortierte Teilfelder Schritt für Schritt zu einem doppelt so großen, sortierten Teilfeld zusammen.


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.
Während [[Quicksort]] die Hauptarbeit bereits beim Aufteilen (Partitionieren) leistet, ist das Teilen bei Mergesort denkbar einfach – '''die eigentliche Sortierarbeit steckt im Mischen'''.


Die Grundidee verfolgt im Vergleich zu [[Quicksort]] eine genau umgekehrte Arbeitsverteilung:
=== Wie funktioniert das Mischen? ===
* '''[[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.
Liegen zwei benachbarte, bereits sortierte Hälften in einem [[Array]] (<code>feld</code>) vor, werden diese mit Hilfe eines temporären Hilfsfelds (<code>hilf</code>) und dreier Zeiger zusammengeführt:
* '''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“).
* '''<code>i</code>''' zeigt auf die vorderste (kleinste noch verfügbare) Zahl der '''linken Hälfte'''.
* '''<code>j</code>''' zeigt auf die vorderste Zahl der '''rechten Hälfte'''.
* '''<code>k</code>''' zeigt auf die nächste freie Stelle im '''Hilfsfeld <code>hilf</code>'''.


=== Wie funktioniert das Verschmelzen (Merge-Schritt)? ===
# Es werden immer nur die beiden vordersten Zahlen <code>feld[i]</code> und <code>feld[j]</code> miteinander verglichen.
Sobald zwei benachbarte Teillisten ('''linke Teilliste''' und '''rechte Teilliste''') sortiert vorliegen, werden sie nach dem Reißverschlussprinzip zusammengeführt:
# Ist <code>feld[i] <= feld[j]</code>, wird die Zahl aus der linken Hälfte in <code>hilf[k]</code> eingetragen und <code>i</code> rückt um 1 weiter. Andernfalls wird die Zahl aus der rechten Hälfte in <code>hilf[k]</code> übernommen und <code>j</code> rückt weiter. In beiden Fällen rückt <code>k</code> auf die nächste freie Stelle. (Durch das <code><=</code> wird bei gleichen Zahlen stets die linke Zahl zuerst übernommen – dadurch bleibt die Reihenfolge gleicher Elemente erhalten und Mergesort ist [[Sortieren#Stabilität|stabil]]).
# Man betrachtet jeweils nur das '''erste (und damit kleinste) Element''' der linken Teilliste und das '''erste Element''' der rechten Teilliste.
# Sobald eine der beiden Hälften vollständig verbraucht ist, wird der '''Rest''' der anderen Hälfte '''ohne weitere Vergleiche''' hinten an das Hilfsfeld angehängt, da diese Zahlen bereits sortiert und größer als alle bisherigen Zahlen sind.
# Beide Elemente werden miteinander verglichen.
# Zum Schluss wird der Inhalt von <code>hilf</code> zurück in das ursprüngliche <code>feld</code> kopiert.
# 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 [[Sortieren#Stabilität|stabil]]).
# Dieser Vergleich wird wiederholt, bis eine der beiden Teillisten vollständig geleert ist.
# 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 [[Speicher]]bedarf: 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''' [[Sortieren#Platzkomplexität – In-place|In-Place]] arbeitet. Anders verhält es sich jedoch bei '''einfach verketteten Listen''', für die Mergesort das optimale Sortierverfahren darstellt.


== Beispiel ==
== 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.
Wir betrachten acht unsortierte Lieferscheine in einem Feld: <code>5, 2, 7, 4, 1, 8, 3, 6</code>.
 
'''1. Teilungsphase (Divide – von oben nach unten):'''
 
Ausgangsliste:
7 10 6 4 9 3 1 5
 
1. Halbierung in der Mitte (je 4 Elemente):
<span style="color:blue">7 10 6 4</span> | <span style="color:red">9 3 1 5</span>
 
2. Halbierung der Teillisten (je 2 Elemente):
<span style="color:blue">7 10</span> | <span style="color:red">6 4</span> &nbsp;&nbsp;und&nbsp;&nbsp; <span style="color:blue">9 3</span> | <span style="color:red">1 5</span>
 
3. Halbierung bis auf einelementige Listen (Rekursionsbasis erreicht):
<span style="color:blue">7</span> | <span style="color:red">10</span> &nbsp;&nbsp; <span style="color:blue">6</span> | <span style="color:red">4</span> &nbsp;&nbsp; <span style="color:blue">9</span> | <span style="color:red">3</span> &nbsp;&nbsp; <span style="color:blue">1</span> | <span style="color:red">5</span>


'''2. Verschmelzungsphase (Merge – von unten nach oben):'''
=== 1. Teilen (von oben nach unten) ===
Das Feld wird schrittweise in der Mitte halbiert, bis nur noch einzelne Zahlen übrig bleiben:
* '''Start (8 Lieferscheine):''' <code>5 2 7 4 1 8 3 6</code>
* '''Hälften (je 4 Zahlen):''' <span style="color:blue">5 2 7 4</span> &nbsp;|&nbsp; <span style="color:red">1 8 3 6</span>
* '''Viertel (je 2 Zahlen):''' <span style="color:blue">5 2</span> &nbsp;|&nbsp; <span style="color:red">7 4</span> &nbsp;&nbsp;und&nbsp;&nbsp; <span style="color:blue">1 8</span> &nbsp;|&nbsp; <span style="color:red">3 6</span>
* '''Einzelne Zahlen (je 1 Zahl – immer sortiert):''' <code>5</code> | <code>2</code> | <code>7</code> | <code>4</code> | <code>1</code> | <code>8</code> | <code>3</code> | <code>6</code>


Nun werden die einelementigen Listen paarweise miteinander verglichen und sortiert zu zweielementigen Listen verschmolzen:
=== 2. Mischen (von unten nach oben) ===
* Aus <span style="color:blue">7</span> und <span style="color:red">10</span> wird '''7 10''' (da 7 < 10)
Nun werden jeweils zwei benachbarte Teile sortiert zusammengemischt:
* Aus <span style="color:blue">6</span> und <span style="color:red">4</span> wird '''4 6''' (da 4 < 6)
* '''Paare mischen:''' Aus <code>5</code> und <code>2</code> wird '''2 5''', aus <code>7</code> und <code>4</code> wird '''4 7'''. Die Paare '''1 8''' und '''3 6''' stehen bereits in der richtigen Reihenfolge.
* Aus <span style="color:blue">9</span> und <span style="color:red">3</span> wird '''3 9''' (da 3 < 9)
* '''Vierer mischen:''' Aus <code>2 5</code> und <code>4 7</code> wird '''2 4 5 7'''. Aus <code>1 8</code> und <code>3 6</code> wird '''1 3 6 8'''.
* Aus <span style="color:blue">1</span> und <span style="color:red">5</span> wird '''1 5''' (da 1 < 5)
* '''Letztes Mischen zum sortierten Feld:''' Die beiden sortierten Hälften <span style="color:blue">2 4 5 7</span> (Index 0 bis 3) und <span style="color:red">1 3 6 8</span> (Index 4 bis 7) werden in das Hilfsfeld <code>hilf</code> gemischt (grau = bereits verbraucht):
*# <code>i = 0, j = 4</code>: Ist 2 &le; 1? '''Nein''' <math>\rightarrow</math> '''1''' ins Hilfsfeld, <code>j</code> rückt weiter. (<code>hilf</code>: '''1''')
*# <code>i = 0, j = 5</code>: Ist 2 &le; 3? '''Ja''' <math>\rightarrow</math> '''2''' ins Hilfsfeld, <code>i</code> rückt weiter. (<code>hilf</code>: '''1 2''')
*# <code>i = 1, j = 5</code>: Ist 4 &le; 3? '''Nein''' <math>\rightarrow</math> '''3''' ins Hilfsfeld, <code>j</code> rückt weiter. (<code>hilf</code>: '''1 2 3''')
*# <code>i = 1, j = 6</code>: Ist 4 &le; 6? '''Ja''' <math>\rightarrow</math> '''4''' ins Hilfsfeld, <code>i</code> rückt weiter. (<code>hilf</code>: '''1 2 3 4''')
*# <code>i = 2, j = 6</code>: Ist 5 &le; 6? '''Ja''' <math>\rightarrow</math> '''5''' ins Hilfsfeld, <code>i</code> rückt weiter. (<code>hilf</code>: '''1 2 3 4 5''')
*# <code>i = 3, j = 6</code>: Ist 7 &le; 6? '''Nein''' <math>\rightarrow</math> '''6''' ins Hilfsfeld, <code>j</code> rückt weiter. (<code>hilf</code>: '''1 2 3 4 5 6''')
*# <code>i = 3, j = 7</code>: Ist 7 &le; 8? '''Ja''' <math>\rightarrow</math> '''7''' ins Hilfsfeld, <code>i</code> rückt weiter. (<code>hilf</code>: '''1 2 3 4 5 6 7''')
*# '''Rest anhängen:''' Links ist nach 7 Vergleichen alles verbraucht (<span style="color:gray">2 4 5 7</span>). Rechts liegt noch die '''8''', die '''ohne Vergleich''' ans Ende von <code>hilf</code> kopiert wird: '''1 2 3 4 5 6 7 8'''. Anschließend wird <code>hilf</code> zurück in <code>feld</code> kopiert.


Zwischenstand nach der ersten Merge-Ebene:
'''Typischer Fehler – Rest vergessen:''' Wird nach der Hauptschleife vergessen, die übrig gebliebenen Zahlen der noch nicht geleerten Hälfte in das Hilfsfeld zu übertragen, steht am Ende <code>1 2 3 4 5 6 7 <span style="color:red">'''0'''</span></code> im Feld, da ein neu angelegtes <code>int</code>-Feld in Java standardmäßig mit Nullen vorinitialisiert ist.
<span style="color:blue">7 10</span> | <span style="color:red">4 6</span> &nbsp;&nbsp;und&nbsp;&nbsp; <span style="color:blue">3 9</span> | <span style="color:red">1 5</span>
 
Als Nächstes verschmelzen wir die linke Teilliste <span style="color:blue">7 10</span> mit der rechten Teilliste <span style="color:red">4 6</span>. Wir vergleichen immer nur die vordersten noch nicht verwendeten Elemente (grau = bereits in die Ergebnisliste übernommen):
# Vergleich <span style="color:blue">'''7''' 10</span> mit <span style="color:red">'''4''' 6</span> <math>\rightarrow</math> '''4''' ist kleiner. Ergebnis bisher: '''4'''
# Vergleich <span style="color:blue">'''7''' 10</span> mit <span style="color:gray">4</span> <span style="color:red">'''6'''</span> <math>\rightarrow</math> '''6''' ist kleiner. Ergebnis bisher: '''4 6'''
# Die rechte (rote) Teilliste ist nun leer! Der Rest der linken Teilliste (<span style="color:blue">7 10</span>) wird komplett angehängt <math>\rightarrow</math> '''4 6 7 10'''.
 
Analog werden auf der rechten Seite <span style="color:blue">3 9</span> und <span style="color:red">1 5</span> zu '''1 3 5 9''' verschmolzen.
 
Im letzten Schritt werden die beiden sortierten Viererlisten <span style="color:blue">4 6 7 10</span> und <span style="color:red">1 3 5 9</span> nach exakt demselben Prinzip zusammengeführt:
* 4 vs. 1 <math>\rightarrow</math> '''1'''
* 4 vs. 3 <math>\rightarrow</math> '''1 3'''
* 4 vs. 5 <math>\rightarrow</math> '''1 3 4'''
* 6 vs. 5 <math>\rightarrow</math> '''1 3 4 5'''
* 6 vs. 9 <math>\rightarrow</math> '''1 3 4 5 6'''
* 7 vs. 9 <math>\rightarrow</math> '''1 3 4 5 6 7'''
* 10 vs. 9 <math>\rightarrow</math> '''1 3 4 5 6 7 9'''
* Rechte Liste leer, Rest (10) anhängen <math>\rightarrow</math> ''1 3 4 5 6 7 9 10''
 
== Pseudocode ==
Der folgende Pseudocode zeigt das Zusammenspiel aus rekursiver Halbierung (<code>mergesort</code>) und dem anschließenden Zusammenführen (<code>verschmelze</code>). <code>links</code> und <code>rechts</code> bezeichnen dabei die Grenzindizes des aktuell betrachteten Bereichs:
 
<syntaxhighlight lang="text">
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
</syntaxhighlight>
 
== Warum Mergesort ideal für einfach verkettete Listen ist ==
Während [[Quicksort]] in der Praxis meist das bevorzugte Verfahren für [[Array|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 [[Speicher]]block abgelegt, sondern als einzelne Knoten-Objekte (<code>Node</code>). Jeder Knoten kennt lediglich seinen eigenen Inhalt (<code>content</code>) und besitzt eine Referenz (<code>nextNode</code>) 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>\mathcal{O}(1)</math> auf jedes beliebige Element <code>array[i]</code> (z. B. das mittlere Element für ''Median-of-Three'') zugreifen. In einer einfach verketteten Liste muss man dafür vom Kopfknoten (<code>head</code>) aus Schritt für Schritt durch die Liste wandern, was <math>\mathcal{O}(n)</math> Zeit kostet.
* '''Kein Rückwärtslaufen möglich:''' Die klassische Partitionierung von [[Quicksort]] lässt zwei Zeiger <code>i</code> (von links nach rechts) und <code>j</code> (von rechts nach links) aufeinander zulaufen. Da eine einfach verkettete Liste keine Rückwärtszeiger (<code>prev</code>) besitzt, kann der Zeiger <code>j</code> nicht rückwärts bewegt werden.
 
=== Vorteile von Mergesort auf einfach verketteten Listen ===
# '''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 (<code>nextNode</code>) weitergeschaltet. Der Algorithmus bewegt sich ausschließlich von vorne nach hinten durch die Datenstruktur.
# '''Kein zusätzlicher Speicher für Hilfsarrays nötig (<math>\mathcal{O}(1)</math> für die Verkettung):''' Auf einem [[Array]] benötigt Mergesort ein Hilfsarray der Größe <math>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 <code>nextNode</code>-Referenzen der Knoten in der richtigen Reihenfolge neu verknüpft („Zeiger umbiegen“). Damit entfällt der größte Nachteil von Mergesort komplett!
# '''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 (<code>slow</code>) geht pro Schleifendurchlauf '''einen''' Knoten weiter, der schnelle Zeiger (<code>fast</code>) springt '''zwei''' Knoten weiter. Sobald <code>fast</code> das Ende der Liste erreicht hat, steht <code>slow</code> exakt in der Mitte. Dort wird die Verbindung (<code>slow.nextNode = null</code>) getrennt.
 
{| class="wikitable"
|+ 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>\mathcal{O}(1)</math> || Durchlauf per ''Fast/Slow-Pointer'' <math>\mathcal{O}(n)</math>
|-
| '''Zusammenführen (Merge)''' || Werte in ein Hilfsarray kopieren <math>\mathcal{O}(n)</math> || Lediglich <code>nextNode</code>-Zeiger umbiegen <math>\mathcal{O}(n)</math>
|-
| '''Zusätzlicher Speicher für Elemente''' || <math>\mathcal{O}(n)</math> (Hilfsarray erforderlich) || <math>\mathcal{O}(1)</math> (keine neuen Knoten nötig)
|}


== Java Implementierung ==
== Java Implementierung ==
Am besten lassen sich komplexe [[Algorithmus|Algorithmen]] nachvollziehen, wenn man sie anhand einer Implementierung mit Hilfe eines [[Debugger|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.
Die Implementierung besteht aus zwei Methoden: <code>mergeSort</code> steuert die rekursive Teilung über die Bereichsgrenzen <code>links</code> und <code>rechts</code>, während <code>mische</code> die beiden sortierten Teilbereiche <code>[links ... mitte]</code> und <code>[mitte + 1 ... rechts]</code> zusammenführt. Gestartet wird die Sortierung für das gesamte Feld mit dem Aufruf <code>mergeSort(feld, 0, feld.length - 1);</code>.
 
=== Implementierung für ein Array ===
In dieser Variante wird ein [[Array]] aus Ganzzahlen (<code>int</code>) sortiert. Die Methode <code>merge</code> nutzt ein temporäres Hilfsarray, um die beiden sortierten Teilbereiche <code>[links ... mitte]</code> und <code>[mitte + 1 ... rechts]</code> geordnet zusammenzuführen.


<syntaxhighlight lang="java">
<syntaxhighlight lang="java">
public void mergeSort(int[] array, int links, int rechts) {
static void mergeSort(int[] feld, int links, int rechts) {
     if (links < rechts) {
     if (links < rechts) {
        // Mitte des aktuellen Bereichs bestimmen
         int mitte = (links + rechts) / 2;
         int mitte = (links + rechts) / 2;
 
         mergeSort(feld, links, mitte);
        // Linke und rechte Hälfte rekursiv sortieren
         mergeSort(feld, mitte + 1, rechts);
         mergeSort(array, links, mitte);
         mische(feld, links, mitte, rechts);
         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) {
static void mische(int[] feld, int links, int mitte, int rechts) {
    // Größen der beiden Teillisten berechnen
     int[] hilf = new int[rechts - links + 1];
     int groesseLinks = mitte - links + 1;
     int i = links, j = mitte + 1, k = 0;
     int groesseRechts = rechts - mitte;


     // Temporäre Hilfsarrays anlegen und Daten hineinkopieren
     while (i <= mitte && j <= rechts) {
    int[] linkesArray = new int[groesseLinks];
         if (feld[i] <= feld[j]) {
    int[] rechtesArray = new int[groesseRechts];
             hilf[k] = feld[i];
 
    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++;
             i++;
         } else {
         } else {
             array[k] = rechtesArray[j];
             hilf[k] = feld[j];
             j++;
             j++;
         }
         }
Zeile 162: Zeile 73:
     }
     }


     // Eventuell verbleibende Restelemente der linken Hälfte anhängen
     // Rest der linken bzw. rechten Hälfte übernehmen
     while (i < groesseLinks) {
     while (i <= mitte) { hilf[k] = feld[i]; i++; k++; }
        array[k] = linkesArray[i];
     while (j <= rechts) { hilf[k] = feld[j]; j++; k++; }
        i++;
        k++;
     }


     // Eventuell verbleibende Restelemente der rechten Hälfte anhängen
     // Zurück ins Feld kopieren (ab Index links)
     while (j < groesseRechts) {
     for (k = 0; k < hilf.length; k++) {
         array[k] = rechtesArray[j];
         feld[links + k] = hilf[k];
        j++;
        k++;
     }
     }
}
}
</syntaxhighlight>
</syntaxhighlight>


=== Implementierung für eine einfach verkettete Liste ===
=== Schreibtischtest (Reihenfolge der Aufrufe) ===
Bei einer einfach verketteten Liste mit einer inneren Klasse <code>Node</code> kommt der Algorithmus vollständig ohne Hilfsarrays aus, da in <code>mergeLists</code> lediglich die <code>nextNode</code>-Verweise der Knoten neu gesetzt werden:
Bei einem Schreibtischtest im Abitur muss die Feldbelegung nach jedem Aufruf von <code>mische</code> angegeben werden. Wichtig: Java arbeitet den Rekursionsbaum '''nicht Ebene für Ebene''' ab, sondern steigt durch den ersten rekursiven Aufruf <code>mergeSort(feld, links, mitte)</code> zuerst in der linken Hälfte komplett in die Tiefe ab, bevor die rechte Hälfte betrachtet wird:


<syntaxhighlight lang="java">
{| class="wikitable"
public class LinkedListMergeSort {
|+ Chronologische Reihenfolge der 7 <code>mische</code>-Aufrufe für <code>5 2 7 4 1 8 3 6</code>
 
! Nr. !! Aufruf !! <code>feld</code> nach dem Aufruf !! Anzahl Vergleiche
    public static class Node {
|-
        int content;
| 1. || <code>mische(0, 0, 1)</code> || '''2 5''' 7 4 1 8 3 6 || 1
        Node nextNode;
|-
 
| 2. || <code>mische(2, 2, 3)</code> || 2 5 '''4 7''' 1 8 3 6 || 1
        public Node(int content) {
|-
            this.content = content;
| 3. || <code>mische(0, 1, 3)</code> || '''2 4 5 7''' 1 8 3 6 || 3
            this.nextNode = null;
|-
        }
| 4. || <code>mische(4, 4, 5)</code> || 2 4 5 7 '''1 8''' 3 6 || 1
    }
|-
 
| 5. || <code>mische(6, 6, 7)</code> || 2 4 5 7 1 8 '''3 6''' || 1
    // 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;
        }
    }
}
</syntaxhighlight>
 
== 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>\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>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>\log_2(n)</math>:
 
{| class="wikitable" style="text-align:center"
|-
|-
! Zu sortierende Elemente <math>n</math>
| 6. || <code>mische(4, 5, 7)</code> || 2 4 5 7 '''1 3 6 8''' || 3
| style="color:green" | 4
| style="color:green" | 8
| style="color:green" | 16
| style="color:green" | 32
|-
|-
! Als Zweierpotenz
| 7. || <code>mische(0, 3, 7)</code> || '''1 2 3 4 5 6 7 8''' || 7
| <math>\color{green}{2^2}</math>
| <math>\color{green}{2^3}</math>
| <math>\color{green}{2^4}</math>
| <math>\color{green}{2^5}</math>
|-
|-
! Anzahl Rekursionsebenen <math>\log_2(n)</math>
! colspan="3" style="text-align:right" | Summe der Vergleiche: || '''17'''
| style="color:red" | 2
| style="color:red" | 3
| style="color:red" | 4
| style="color:red" | 5
|}
|}


Nun bestimmen wir den Aufwand pro Ebene beim Zusammenführen (<code>merge</code>):
== Mergesort auf verketteten Listen ==
* Auf einer Ebene mit <math>k</math> Teilproblemen der Größe <math>\frac{n}{k}</math> wird beim Verschmelzen jedes der insgesamt <math>n</math> Elemente genau einmal in die Hand genommen, verglichen und an seine neue Position übertragen.
Während auf einem [[Array]] oft [[Quicksort]] bevorzugt wird, weil Mergesort dort ein zusätzliches Hilfsfeld <code>hilf</code> benötigt, ist '''Mergesort das optimale Sortierverfahren für verkettete Listen''' – insbesondere schon für '''einfach verkettete Listen''', deren Knoten lediglich eine Referenz <code>naechster</code> auf den Nachfolger, aber keinen Verweis <code>vorgaenger</code> besitzen:
* Der Arbeitsaufwand auf '''jeder einzelnen Ebene''' ist in der Summe über alle Teillisten hinweg also immer linear proportional zu <math>n</math>, das heißt <math>\mathcal{O}(n)</math>.


Multiplizieren wir die Arbeit pro Ebene (<math>n</math> Operationen) mit der Anzahl der Ebenen (<math>\log_2(n)</math>), ergibt sich unabhängig von der Vorsortierung der Eingabedaten:
* '''Warum [[Quicksort]] und Insertion Sort eine zweifach verkettete Liste benötigen:'''
:<math>T(n) = n \cdot \log_2(n)</math>
** Bei '''[[Quicksort]]''' wird für den rekursiven Aufruf der linken Teilliste der Knoten unmittelbar ''vor'' dem Pivot-Knoten als neue rechte Grenze benötigt. Nur in einer bidirektionalen (zweifach verketteten) Liste mit <code>vorgaenger</code>-Zeiger und <code>endeKnoten</code> ist dieser Zugriff über <code>pivotKnoten.getVorgaenger()</code> direkt in <math>\mathcal{O}(1)</math> möglich. Auf einer einfach verketteten Liste müsste man den Vorgänger jedes Mal vom <code>startKnoten</code> aus in <math>\mathcal{O}(n)</math> suchen.
** Auch '''Insertion Sort''' profitiert stark von einer Doppelverkettung, da der Suchzeiger über <code>getVorgaenger()</code> direkt vom aktuellen Element aus rückwärts durch den sortierten Bereich wandern kann, statt jedes Mal beim <code>startKnoten</code> neu zu beginnen.
* '''Warum Mergesort bereits auf einer einfach verketteten Liste ideal arbeitet:'''
*# '''Reine Vorwärtsnavigation über <code>naechster</code>:''' Beim Mischen zweier sortierter Teillisten werden immer nur die vordersten Knoten verglichen und über <code>getNaechster()</code> in Vorwärtsrichtung weitergeschaltet. Ein <code>vorgaenger</code>-Zeiger bringt für Mergesort keinen Vorteil, weil niemals rückwärts navigiert werden muss. Auch die Listenmitte lässt sich vorwärts bestimmen (ein langsamer Zeiger rückt einen Knoten weiter, ein schneller Zeiger zwei Knoten).
*# '''Kein Hilfsfeld <code>hilf</code> nötig (<math>\mathcal{O}(1)</math> Zusatzspeicher für Knoten):''' Auf einer verketteten Liste müssen beim Mischen keine neuen Knoten im [[Speicher]] angelegt und keine Daten in ein Hilfsfeld kopiert werden. Stattdessen werden einfach die vorhandenen <code>naechster</code>-Zeiger (<code>setNaechster(...)</code>) der Knoten in der sortierten Reihenfolge neu verknüpft. Damit entfällt der Speicher-Nachteil von Mergesort auf verketteten Listen vollständig.


* '''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>\frac{m}{2}</math> sind im besten Fall <math>\frac{m}{2}</math> Vergleiche nötig, da eine Hälfte sofort komplett kleiner ist als die andere). Da jedoch auf jeder der <math>\log_2(n)</math> Ebenen weiterhin alle <math>n</math> Elemente zusammengeführt werden müssen, liegt die Laufzeit bei <math>\mathcal{O}(n \log n)</math>.
== Laufzeitanalyse ==
* '''Average-Case (Durchschnittlicher Fall):''' Bei zufällig verteilten Daten beträgt die Laufzeit <math>\mathcal{O}(n \log n)</math>.
Für die [[Laufzeitanalyse]] betrachten wir die Anzahl der Teilungsebenen und die Anzahl der Vergleiche pro Ebene:
* '''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 <code>1 3 5 7</code> und <code>2 4 6 8</code>). Selbst dann sind pro Ebene maximal <math>n - 1</math> Vergleiche nötig. Ein Entarten des Baumes zu einer Kette wie bei [[Quicksort]] (<math>\mathcal{O}(n^2)</math>) ist bei Mergesort '''ausgeschlossen'''. Die Laufzeit beträgt auch im Worst-Case garantiert <math>\mathcal{O}(n \log n)</math>.
* '''Anzahl der Ebenen:''' Da das Feld in jedem Schritt halbiert wird (<math>8 \rightarrow 4 \rightarrow 2 \rightarrow 1</math>), lässt sich ein Feld mit <math>n</math> Zahlen genau <math>\log_2(n)</math>-mal teilen (bei <math>n = 8</math> sind es <math>\log_2(8) = 3</math> Ebenen).
* '''Vergleiche pro Ebene:''' Auf jeder Ebene wird mit jedem Vergleich genau eine Zahl in das Hilfsfeld übertragen. Für <math>n</math> Zahlen sind pro Ebene also '''höchstens <math>n</math> Vergleiche''' nötig.


=== Platzkomplexität (Speicherbedarf) ===
Multipliziert man die <math>\log_2(n)</math> Ebenen mit höchstens <math>n</math> Vergleichen pro Ebene, benötigt Mergesort insgesamt höchstens <math>n \cdot \log_2(n)</math> Vergleiche (bei <math>n = 8</math> höchstens <math>8 \cdot 3 = 24</math> Vergleiche, in unserem Beispiel tatsächlich <math>17</math>).
Bei der Bewertung der [[Sortieren#Platzkomplexität – In-place|Platzkomplexität]] muss zwischen den beiden Datenstrukturen unterschieden werden:
 
* '''Auf einem [[Array]]:''' Da das Hilfsarray beim Verschmelzen bis zu <math>n</math> Elemente aufnehmen muss (hinzu kommen <math>\mathcal{O}(\log n)</math> Speicherrahmen auf dem Aufruf-[[Stapel|Stack]] für die Rekursion), beträgt die Platzkomplexität <math>\mathcal{O}(n)</math>.
Da Mergesort das Feld unabhängig von den gespeicherten Zahlen immer stur in der Mitte teilt, kann der Aufrufbaum niemals wie bei [[Quicksort]] entarten:
* '''Auf einer einfach verketteten Liste:''' Da lediglich Zeiger umgebogen und keine neuen Knoten erzeugt werden, wird nur der Speicherplatz für die <math>\log_2(n)</math> geschachtelten Rekursionsaufrufe auf dem Call-Stack benötigt. Die Platzkomplexität sinkt dadurch auf <math>\mathcal{O}(\log n)</math> (bzw. bei einer iterativen Bottom-Up-Implementierung sogar auf <math>\mathcal{O}(1)</math>).
* '''Best-Case, Average-Case und Worst-Case:''' In allen drei Fällen beträgt die Zeitkomplexität garantiert <math>\mathcal{O}(n \cdot \log n)</math>.
* '''[[Sortieren#Platzkomplexität – In-place|Platzkomplexität]]:''' Auf einem [[Array]] wird zusätzlicher [[Speicher]] in <math>\mathcal{O}(n)</math> für das Hilfsfeld <code>hilf</code> benötigt (nicht In-Place). Auf einer verketteten Liste werden nur Zeiger umgebogen, sodass kein Hilfsfeld nötig ist.
 
=== Laufzeitvergleich: Bubblesort vs. Mergesort ===
Der enorme Geschwindigkeitsvorteil von <math>\mathcal{O}(n \cdot \log n)</math> gegenüber quadratischen Verfahren wie [[Bubblesort]] (<math>\mathcal{O}(n^2)</math> mit <math>\frac{n(n-1)}{2}</math> Vergleichen) zeigt sich besonders bei großen Datenmengen:


=== Direkter Vergleich: Mergesort vs. Quicksort ===
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|-
|-
! Eigenschaft !! Mergesort !! [[Quicksort]]
! Anzahl Elemente <math>n</math> !! [[Bubblesort]]<br><math>\frac{n(n-1)}{2}</math> Vergleiche !! Mergesort<br>höchstens <math>n \cdot \log_2(n)</math> Vergleiche
|-
|-
| '''Best-Case Zeitkomplexität''' || <math>\mathcal{O}(n \log n)</math> || <math>\mathcal{O}(n \log n)</math>
| '''8''' || 28 || 24 (im Beispiel 17)
|-
|-
| '''Average-Case Zeitkomplexität''' || <math>\mathcal{O}(n \log n)</math> || <math>\mathcal{O}(n \log n)</math>
| '''1.000''' || 499.500 || <math>\approx</math> 10.000
|-
|-
| '''Worst-Case Zeitkomplexität''' || style="color:green" | '''<math>\mathcal{O}(n \log n)</math>''' || style="color:red" | '''<math>\mathcal{O}(n^2)</math>'''
| '''1.000.000''' || <math>\approx</math> 500 Mrd. || <math>\approx</math> 20 Mio.
|-
| '''Platzkomplexität (auf [[Array]])''' || style="color:red" | <math>\mathcal{O}(n)</math> (nicht [[Sortieren#Platzkomplexität – In-place|In-Place]]) || style="color:green" | <math>\mathcal{O}(\log n)</math> ([[Sortieren#Platzkomplexität – In-place|In-Place]])
|-
| '''[[Sortieren#Stabilität|Stabilität]]''' || style="color:green" | '''Ja (stabil)''' || style="color:red" | Nein (in der Regel instabil)
|-
| '''Optimale Datenstruktur''' || '''Einfach verkettete Listen''' || '''[[Array|Arrays]]'''
|}
|}
''Rechenbeispiel:'' Ein Rechner, der 1 Milliarde Vergleiche pro Sekunde ausführt, benötigt für eine Million Zahlen mit [[Bubblesort]] '''gut 8 Minuten''', mit Mergesort hingegen '''nur 0,02 Sekunden'''.


[[Kategorie:Programmierung]]
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Version vom 7. November 2026, 13:10 Uhr

Einführung

Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu Quicksort auch stabiler Sortieralgorithmus ist der Mergesort (Sortieren durch Mischen). Er funktioniert nach dem Prinzip „Teile und herrsche“ (Divide and Conquer), bei dem aus einem großen Problem zwei kleinere Teilprobleme gemacht werden, was in der Programmierung mithilfe von Rekursion umgesetzt wird.

Die Grundidee gliedert sich in zwei Phasen:

  • Teilen: Das zu sortierende Feld wird fortlaufend in der Mitte in zwei Hälften geteilt, bis jedes Teilfeld nur noch aus einer einzigen Zahl besteht. Da eine einzelne Zahl für sich genommen immer sortiert ist, endet hier das Teilen (Abbruch der Rekursion).
  • Mischen: Anschließend geht der Algorithmus den Weg wieder zurück und mischt jeweils zwei benachbarte, bereits sortierte Teilfelder Schritt für Schritt zu einem doppelt so großen, sortierten Teilfeld zusammen.

Während Quicksort die Hauptarbeit bereits beim Aufteilen (Partitionieren) leistet, ist das Teilen bei Mergesort denkbar einfach – die eigentliche Sortierarbeit steckt im Mischen.

Wie funktioniert das Mischen?

Liegen zwei benachbarte, bereits sortierte Hälften in einem Array (feld) vor, werden diese mit Hilfe eines temporären Hilfsfelds (hilf) und dreier Zeiger zusammengeführt:

  • i zeigt auf die vorderste (kleinste noch verfügbare) Zahl der linken Hälfte.
  • j zeigt auf die vorderste Zahl der rechten Hälfte.
  • k zeigt auf die nächste freie Stelle im Hilfsfeld hilf.
  1. Es werden immer nur die beiden vordersten Zahlen feld[i] und feld[j] miteinander verglichen.
  2. Ist feld[i] <= feld[j], wird die Zahl aus der linken Hälfte in hilf[k] eingetragen und i rückt um 1 weiter. Andernfalls wird die Zahl aus der rechten Hälfte in hilf[k] übernommen und j rückt weiter. In beiden Fällen rückt k auf die nächste freie Stelle. (Durch das <= wird bei gleichen Zahlen stets die linke Zahl zuerst übernommen – dadurch bleibt die Reihenfolge gleicher Elemente erhalten und Mergesort ist stabil).
  3. Sobald eine der beiden Hälften vollständig verbraucht ist, wird der Rest der anderen Hälfte ohne weitere Vergleiche hinten an das Hilfsfeld angehängt, da diese Zahlen bereits sortiert und größer als alle bisherigen Zahlen sind.
  4. Zum Schluss wird der Inhalt von hilf zurück in das ursprüngliche feld kopiert.

Beispiel

Wir betrachten acht unsortierte Lieferscheine in einem Feld: 5, 2, 7, 4, 1, 8, 3, 6.

1. Teilen (von oben nach unten)

Das Feld wird schrittweise in der Mitte halbiert, bis nur noch einzelne Zahlen übrig bleiben:

  • Start (8 Lieferscheine): 5 2 7 4 1 8 3 6
  • Hälften (je 4 Zahlen): 5 2 7 4  |  1 8 3 6
  • Viertel (je 2 Zahlen): 5 2  |  7 4   und   1 8  |  3 6
  • Einzelne Zahlen (je 1 Zahl – immer sortiert): 5 | 2 | 7 | 4 | 1 | 8 | 3 | 6

2. Mischen (von unten nach oben)

Nun werden jeweils zwei benachbarte Teile sortiert zusammengemischt:

  • Paare mischen: Aus 5 und 2 wird 2 5, aus 7 und 4 wird 4 7. Die Paare 1 8 und 3 6 stehen bereits in der richtigen Reihenfolge.
  • Vierer mischen: Aus 2 5 und 4 7 wird 2 4 5 7. Aus 1 8 und 3 6 wird 1 3 6 8.
  • Letztes Mischen zum sortierten Feld: Die beiden sortierten Hälften 2 4 5 7 (Index 0 bis 3) und 1 3 6 8 (Index 4 bis 7) werden in das Hilfsfeld hilf gemischt (grau = bereits verbraucht):
    1. i = 0, j = 4: Ist 2 ≤ 1? Nein [math]\displaystyle{ \rightarrow }[/math] 1 ins Hilfsfeld, j rückt weiter. (hilf: 1)
    2. i = 0, j = 5: Ist 2 ≤ 3? Ja [math]\displaystyle{ \rightarrow }[/math] 2 ins Hilfsfeld, i rückt weiter. (hilf: 1 2)
    3. i = 1, j = 5: Ist 4 ≤ 3? Nein [math]\displaystyle{ \rightarrow }[/math] 3 ins Hilfsfeld, j rückt weiter. (hilf: 1 2 3)
    4. i = 1, j = 6: Ist 4 ≤ 6? Ja [math]\displaystyle{ \rightarrow }[/math] 4 ins Hilfsfeld, i rückt weiter. (hilf: 1 2 3 4)
    5. i = 2, j = 6: Ist 5 ≤ 6? Ja [math]\displaystyle{ \rightarrow }[/math] 5 ins Hilfsfeld, i rückt weiter. (hilf: 1 2 3 4 5)
    6. i = 3, j = 6: Ist 7 ≤ 6? Nein [math]\displaystyle{ \rightarrow }[/math] 6 ins Hilfsfeld, j rückt weiter. (hilf: 1 2 3 4 5 6)
    7. i = 3, j = 7: Ist 7 ≤ 8? Ja [math]\displaystyle{ \rightarrow }[/math] 7 ins Hilfsfeld, i rückt weiter. (hilf: 1 2 3 4 5 6 7)
    8. Rest anhängen: Links ist nach 7 Vergleichen alles verbraucht (2 4 5 7). Rechts liegt noch die 8, die ohne Vergleich ans Ende von hilf kopiert wird: 1 2 3 4 5 6 7 8. Anschließend wird hilf zurück in feld kopiert.

Typischer Fehler – Rest vergessen: Wird nach der Hauptschleife vergessen, die übrig gebliebenen Zahlen der noch nicht geleerten Hälfte in das Hilfsfeld zu übertragen, steht am Ende 1 2 3 4 5 6 7 0 im Feld, da ein neu angelegtes int-Feld in Java standardmäßig mit Nullen vorinitialisiert ist.

Java Implementierung

Die Implementierung besteht aus zwei Methoden: mergeSort steuert die rekursive Teilung über die Bereichsgrenzen links und rechts, während mische die beiden sortierten Teilbereiche [links ... mitte] und [mitte + 1 ... rechts] zusammenführt. Gestartet wird die Sortierung für das gesamte Feld mit dem Aufruf mergeSort(feld, 0, feld.length - 1);.

static void mergeSort(int[] feld, int links, int rechts) {
    if (links < rechts) {
        int mitte = (links + rechts) / 2;
        mergeSort(feld, links, mitte);
        mergeSort(feld, mitte + 1, rechts);
        mische(feld, links, mitte, rechts);
    }
}

static void mische(int[] feld, int links, int mitte, int rechts) {
    int[] hilf = new int[rechts - links + 1];
    int i = links, j = mitte + 1, k = 0;

    while (i <= mitte && j <= rechts) {
        if (feld[i] <= feld[j]) {
            hilf[k] = feld[i];
            i++;
        } else {
            hilf[k] = feld[j];
            j++;
        }
        k++;
    }

    // Rest der linken bzw. rechten Hälfte übernehmen
    while (i <= mitte)  { hilf[k] = feld[i]; i++; k++; }
    while (j <= rechts) { hilf[k] = feld[j]; j++; k++; }

    // Zurück ins Feld kopieren (ab Index links)
    for (k = 0; k < hilf.length; k++) {
        feld[links + k] = hilf[k];
    }
}

Schreibtischtest (Reihenfolge der Aufrufe)

Bei einem Schreibtischtest im Abitur muss die Feldbelegung nach jedem Aufruf von mische angegeben werden. Wichtig: Java arbeitet den Rekursionsbaum nicht Ebene für Ebene ab, sondern steigt durch den ersten rekursiven Aufruf mergeSort(feld, links, mitte) zuerst in der linken Hälfte komplett in die Tiefe ab, bevor die rechte Hälfte betrachtet wird:

Chronologische Reihenfolge der 7 mische-Aufrufe für 5 2 7 4 1 8 3 6
Nr. Aufruf feld nach dem Aufruf Anzahl Vergleiche
1. mische(0, 0, 1) 2 5 7 4 1 8 3 6 1
2. mische(2, 2, 3) 2 5 4 7 1 8 3 6 1
3. mische(0, 1, 3) 2 4 5 7 1 8 3 6 3
4. mische(4, 4, 5) 2 4 5 7 1 8 3 6 1
5. mische(6, 6, 7) 2 4 5 7 1 8 3 6 1
6. mische(4, 5, 7) 2 4 5 7 1 3 6 8 3
7. mische(0, 3, 7) 1 2 3 4 5 6 7 8 7
Summe der Vergleiche: 17

Mergesort auf verketteten Listen

Während auf einem Array oft Quicksort bevorzugt wird, weil Mergesort dort ein zusätzliches Hilfsfeld hilf benötigt, ist Mergesort das optimale Sortierverfahren für verkettete Listen – insbesondere schon für einfach verkettete Listen, deren Knoten lediglich eine Referenz naechster auf den Nachfolger, aber keinen Verweis vorgaenger besitzen:

  • Warum Quicksort und Insertion Sort eine zweifach verkettete Liste benötigen:
    • Bei Quicksort wird für den rekursiven Aufruf der linken Teilliste der Knoten unmittelbar vor dem Pivot-Knoten als neue rechte Grenze benötigt. Nur in einer bidirektionalen (zweifach verketteten) Liste mit vorgaenger-Zeiger und endeKnoten ist dieser Zugriff über pivotKnoten.getVorgaenger() direkt in [math]\displaystyle{ \mathcal{O}(1) }[/math] möglich. Auf einer einfach verketteten Liste müsste man den Vorgänger jedes Mal vom startKnoten aus in [math]\displaystyle{ \mathcal{O}(n) }[/math] suchen.
    • Auch Insertion Sort profitiert stark von einer Doppelverkettung, da der Suchzeiger über getVorgaenger() direkt vom aktuellen Element aus rückwärts durch den sortierten Bereich wandern kann, statt jedes Mal beim startKnoten neu zu beginnen.
  • Warum Mergesort bereits auf einer einfach verketteten Liste ideal arbeitet:
    1. Reine Vorwärtsnavigation über naechster: Beim Mischen zweier sortierter Teillisten werden immer nur die vordersten Knoten verglichen und über getNaechster() in Vorwärtsrichtung weitergeschaltet. Ein vorgaenger-Zeiger bringt für Mergesort keinen Vorteil, weil niemals rückwärts navigiert werden muss. Auch die Listenmitte lässt sich vorwärts bestimmen (ein langsamer Zeiger rückt einen Knoten weiter, ein schneller Zeiger zwei Knoten).
    2. Kein Hilfsfeld hilf nötig ([math]\displaystyle{ \mathcal{O}(1) }[/math] Zusatzspeicher für Knoten): Auf einer verketteten Liste müssen beim Mischen keine neuen Knoten im Speicher angelegt und keine Daten in ein Hilfsfeld kopiert werden. Stattdessen werden einfach die vorhandenen naechster-Zeiger (setNaechster(...)) der Knoten in der sortierten Reihenfolge neu verknüpft. Damit entfällt der Speicher-Nachteil von Mergesort auf verketteten Listen vollständig.

Laufzeitanalyse

Für die Laufzeitanalyse betrachten wir die Anzahl der Teilungsebenen und die Anzahl der Vergleiche pro Ebene:

  • Anzahl der Ebenen: Da das Feld in jedem Schritt halbiert wird ([math]\displaystyle{ 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 }[/math]), lässt sich ein Feld mit [math]\displaystyle{ n }[/math] Zahlen genau [math]\displaystyle{ \log_2(n) }[/math]-mal teilen (bei [math]\displaystyle{ n = 8 }[/math] sind es [math]\displaystyle{ \log_2(8) = 3 }[/math] Ebenen).
  • Vergleiche pro Ebene: Auf jeder Ebene wird mit jedem Vergleich genau eine Zahl in das Hilfsfeld übertragen. Für [math]\displaystyle{ n }[/math] Zahlen sind pro Ebene also höchstens [math]\displaystyle{ n }[/math] Vergleiche nötig.

Multipliziert man die [math]\displaystyle{ \log_2(n) }[/math] Ebenen mit höchstens [math]\displaystyle{ n }[/math] Vergleichen pro Ebene, benötigt Mergesort insgesamt höchstens [math]\displaystyle{ n \cdot \log_2(n) }[/math] Vergleiche (bei [math]\displaystyle{ n = 8 }[/math] höchstens [math]\displaystyle{ 8 \cdot 3 = 24 }[/math] Vergleiche, in unserem Beispiel tatsächlich [math]\displaystyle{ 17 }[/math]).

Da Mergesort das Feld unabhängig von den gespeicherten Zahlen immer stur in der Mitte teilt, kann der Aufrufbaum niemals wie bei Quicksort entarten:

  • Best-Case, Average-Case und Worst-Case: In allen drei Fällen beträgt die Zeitkomplexität garantiert [math]\displaystyle{ \mathcal{O}(n \cdot \log n) }[/math].
  • Platzkomplexität: Auf einem Array wird zusätzlicher Speicher in [math]\displaystyle{ \mathcal{O}(n) }[/math] für das Hilfsfeld hilf benötigt (nicht In-Place). Auf einer verketteten Liste werden nur Zeiger umgebogen, sodass kein Hilfsfeld nötig ist.

Laufzeitvergleich: Bubblesort vs. Mergesort

Der enorme Geschwindigkeitsvorteil von [math]\displaystyle{ \mathcal{O}(n \cdot \log n) }[/math] gegenüber quadratischen Verfahren wie Bubblesort ([math]\displaystyle{ \mathcal{O}(n^2) }[/math] mit [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] Vergleichen) zeigt sich besonders bei großen Datenmengen:

Anzahl Elemente [math]\displaystyle{ n }[/math] Bubblesort
[math]\displaystyle{ \frac{n(n-1)}{2} }[/math] Vergleiche
Mergesort
höchstens [math]\displaystyle{ n \cdot \log_2(n) }[/math] Vergleiche
8 28 24 (im Beispiel 17)
1.000 499.500 [math]\displaystyle{ \approx }[/math] 10.000
1.000.000 [math]\displaystyle{ \approx }[/math] 500 Mrd. [math]\displaystyle{ \approx }[/math] 20 Mio.

Rechenbeispiel: Ein Rechner, der 1 Milliarde Vergleiche pro Sekunde ausführt, benötigt für eine Million Zahlen mit Bubblesort gut 8 Minuten, mit Mergesort hingegen nur 0,02 Sekunden.