Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Mergesort sortiert ein Array nach dem Teile-und-Herrsche-Prinzip: Array halbieren, beide Hälften rekursiv sortieren, dann zu einem sortierten Ganzen verschmelzen. Garantiert O(n log n), unabhängig von der Eingabe-Reihenfolge.
Was du in der Klausur können musst:
Idee in 3 Schritten: Teile (Array in der Mitte), Sortiere (beide Hälften rekursiv), Merge (sortiere zusammen)
Komplexität: O(n log n) im Best-, Average- und Worst-Case
In-Place: nein, braucht O(n) zusätzlichen Speicher für das Merge
Stabil: ja, gleiche Werte behalten ihre Reihenfolge
In Klausuren ist Mergesort oft die Wahl wenn die Aufgabe garantierte O(n log n) oder Stabilität verlangt. Quicksort hat schlechteren Worst-Case (O(n²)), Mergesort braucht aber zusätzlichen Speicher.
Teile das Array in der Mitte.
Sortiere beide Hälften, rekursiv mit Mergesort.
Merge die zwei sortierten Hälften zu einem sortierten Ganzen.
Der Merge-Schritt ist der Trick: zwei sortierte Listen lassen sich in O(n) zu einer sortierten Liste verschmelzen, du musst nur immer das kleinere der beiden Köpfe nehmen.
Bei externer Sortierung (Daten passen nicht in den Speicher)
Java's Arrays.sort() für Objekte nutzt eine Mergesort-Variante (Timsort).
Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen
▾
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Erklärung
Mergesort
Mergesort sortiert ein Array nach dem Teile-und-Herrsche-Prinzip: Array halbieren, beide Hälften rekursiv sortieren, dann zu einem sortierten Ganzen verschmelzen. Garantiert O(n log n), unabhängig von der Eingabe-Reihenfolge.
Idee in 3 Schritten: Teile (Array in der Mitte), Sortiere (beide Hälften rekursiv), Merge (sortiere zusammen)
Komplexität: O(n log n) im Best-, Average- und Worst-Case
In-Place: nein, braucht O(n) zusätzlichen Speicher für das Merge
Stabil: ja, gleiche Werte behalten ihre Reihenfolge
In Klausuren ist Mergesort oft die Wahl wenn die Aufgabe garantierte O(n log n) oder Stabilität verlangt. Quicksort hat schlechteren Worst-Case (O(n²)), Mergesort braucht aber zusätzlichen Speicher.
Die Idee in 3 Schritten
Teile das Array in der Mitte.
Sortiere beide Hälften, rekursiv mit Mergesort.
Merge die zwei sortierten Hälften zu einem sortierten Ganzen.
Der Merge-Schritt ist der Trick: zwei sortierte Listen lassen sich in O(n) zu einer sortierten Liste verschmelzen, du musst nur immer das kleinere der beiden Köpfe nehmen.
Bei externer Sortierung (Daten passen nicht in den Speicher)
Java's Arrays.sort() für Objekte nutzt eine Mergesort-Variante (Timsort).
Teil 2·Visualisierung / Interaktiv
Interaktiv
Mergesort live
Schau wie Mergesort sein Ergebnis aus immer größeren sortierten Blöcken zusammenbaut. Du siehst die Schreiboperationen, weil jedes Element beim Merge in einen Hilfsarray kopiert und dann zurückgeschrieben wird.
Probier folgendes:
n = 16: log₂(16) = 4 Halbierungs-Ebenen, ~50 Vergleiche
n = 32: 5 Ebenen, ~120 Vergleiche
Jede Verdopplung von n: ~Faktor 2,2 mehr Arbeit (nicht 4×)
Interaktive Visualisierung
Animiert mehrere Sortier-Algorithmen parallel mit Vergleichs- und Tausch-Counter.
Faustregel zum Mitnehmen: Mergesort ist robust. Egal welche Eingabe (zufällig, sortiert, umgekehrt sortiert): immer dieselbe O(n log n)-Performance. Das ist sein größter Vorteil gegenüber Quicksort.
Teil 3·Quiz / Klausurfragen
Quiz
Klausurfragen mit Lösungen (6)
F1.Warum ist Mergesort schneller als Bubblesort bei großen Arrays?
Antwort: Mergesort halbiert das Problem rekursiv (Divide & Conquer)
Erklärung: Durch das rekursive Halbieren ergibt sich eine logarithmische Tiefe (log₂ n Ebenen). Auf jeder Ebene wird das gesamte Array einmal merged → O(n log n) statt O(n²).
F2.Welche Aussage über Mergesort stimmt?
Antwort: Mergesort braucht O(n) Zusatzspeicher
Erklärung: Mergesort kopiert beim Merge-Schritt die Elemente in einen Hilfsarray, daher O(n) Zusatzspeicher. Aber: garantiert O(n log n), egal welche Eingabe, kein Worst-Case-Abrutschen wie bei Quicksort.
F3.Ein Array mit 1024 Elementen wird mit Mergesort sortiert. Wie tief ist die Rekursion (Anzahl der Halbierungs-Ebenen)?
Antwort: ~10
Erklärung: log₂(1024) = 10. Mergesort halbiert 10× bis Arrays der Größe 1 erreicht sind. Das ist die logarithmische Tiefe, die O(n log n) erklärt.
F4.Du sortierst Studenten erst nach Note, dann nach Name. Welche Mergesort-Eigenschaft brauchst du dafür?
Antwort: Stabilität
Erklärung: Bei mehrfachem Sortieren brauchst du Stabilität: gleiche Schlüssel müssen ihre Reihenfolge behalten. Mergesort ist stabil, daher bleibt nach dem zweiten Sort die alphabetische Reihenfolge bei gleicher Note erhalten.
F5.Mergesort ist im Worst Case schneller als Quicksort.
Antwort: Wahr
Erklärung: Mergesort hat garantiert `O(n log n)` in jedem Fall. Quicksort kann auf `O(n²)` abrutschen bei ungünstiger Pivot-Wahl (z.B. sortierter Input mit naivem Pivot). Daher: Worst Case → Mergesort schneller. Average Case ist Quicksort meist schneller (Cache-Lokalität, in-place).
Typ: Wahr/Falsch
F6.Welche der folgenden Aussagen über Mergesort sind richtig?
Richtige Antworten: Mergesort ist stabil; Mergesort braucht O(n) Zusatzspeicher; Mergesort hat O(n log n) auch im Worst Case; Mergesort ist parallelisierbar (Hälften unabhängig sortierbar)
Erklärung: Stabil ✓, O(n) Speicher ✓, garantiert O(n log n) ✓, parallelisierbar ✓. NICHT in-place — Mergesort braucht ein Hilfs-Array für den Merge-Schritt. Das ist der Hauptnachteil gegenüber Quicksort.