Zum Inhalt springen

Mergesort: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Keine Bearbeitungszusammenfassung
K 1 Version importiert
 
(Eine dazwischenliegende Version von einem anderen Benutzer wird nicht angezeigt)
Zeile 1: Zeile 1:
== Einführung ==
== Einführung ==
<html>
{{#ev:youtube|KuNLzdRnwTU|320|poster=Datei:Vorschau YouTube KuNLzdRnwTU.jpg|title=Mergesort Schritt für Schritt – mit Java-Code}}
<iframe width="280" height="157.5" src="https://www.youtube.com/embed/KuNLzdRnwTU?si=KiaHZg2E0XRDmgV7" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
</html>


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.
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.
Zeile 20: Zeile 18:
# Es werden immer nur die beiden vordersten Zahlen <code>feld[i]</code> und <code>feld[j]</code> miteinander verglichen.
# Es werden immer nur die beiden vordersten Zahlen <code>feld[i]</code> und <code>feld[j]</code> miteinander verglichen.
# 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]]).
# 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]]).
# 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.
# 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 mindestens so groß wie alle bisherigen Zahlen sind.
# Zum Schluss wird der Inhalt von <code>hilf</code> zurück in das ursprüngliche <code>feld</code> kopiert.
# Zum Schluss wird der Inhalt von <code>hilf</code> zurück in das ursprüngliche <code>feld</code> kopiert.


Zeile 89: Zeile 87:


=== Schreibtischtest (Reihenfolge der Aufrufe) ===
=== Schreibtischtest (Reihenfolge der Aufrufe) ===
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:
Bei einem Schreibtischtest im Abitur wird üblicherweise die Feldbelegung nach jedem Aufruf von <code>mische</code> angegeben. 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:


{| class="wikitable"
{| class="wikitable"
Zeile 115: Zeile 113:
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:
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:


* '''Warum [[Quicksort]] und Insertion Sort eine zweifach verkettete Liste benötigen:'''
* '''Warum [[Quicksort]] und Insertion Sort in den hier betrachteten Implementierungen einen Vorgängerzeiger nutzen (zweifach verkettete Liste):'''
** 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.
** 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.
** 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.
** Dabei bezeichnet <code>startKnoten</code> den ersten und <code>endeKnoten</code> den letzten Knoten der betrachteten Teilliste, <code>pivotKnoten</code> den Pivot-Knoten. <code>getVorgaenger()</code> liefert den Vorgängerknoten, <code>getNaechster()</code> und <code>setNaechster(...)</code> lesen und setzen den Nachfolger eines Knotens.
* '''Warum Mergesort bereits auf einer einfach verketteten Liste ideal arbeitet:'''
* '''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).
*# '''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).
Zeile 124: Zeile 123:
== Laufzeitanalyse ==
== Laufzeitanalyse ==
Für die [[Laufzeitanalyse]] betrachten wir die Anzahl der Teilungsebenen und die Anzahl der Vergleiche pro Ebene:
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>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).
* '''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 höchstens <math>\lceil \log_2(n) \rceil</math>-mal teilen (bei <math>n = 8</math> genau <math>\log_2(8) = 3</math>-mal, also in 3 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.
* '''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.



Aktuelle Version vom 15. November 2026, 18:24 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 mindestens so groß wie 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 wird üblicherweise die Feldbelegung nach jedem Aufruf von mische angegeben. 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 in den hier betrachteten Implementierungen einen Vorgängerzeiger nutzen (zweifach verkettete Liste):
    • 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.
    • Dabei bezeichnet startKnoten den ersten und endeKnoten den letzten Knoten der betrachteten Teilliste, pivotKnoten den Pivot-Knoten. getVorgaenger() liefert den Vorgängerknoten, getNaechster() und setNaechster(...) lesen und setzen den Nachfolger eines Knotens.
  • 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 höchstens [math]\displaystyle{ \lceil \log_2(n) \rceil }[/math]-mal teilen (bei [math]\displaystyle{ n = 8 }[/math] genau [math]\displaystyle{ \log_2(8) = 3 }[/math]-mal, also in 3 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.