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:
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.
Der Merge-Schritt ist der Trick: zwei sortierte Listen lassen sich in zu einer sortierten Liste verschmelzen, du musst nur immer das kleinere der beiden Köpfe nehmen.
[5, 2, 8, 1, 9, 3, 7, 4]
↓ teilen
[5, 2, 8, 1] [9, 3, 7, 4]
↓ teilen
[5, 2] [8, 1] [9, 3] [7, 4]
↓ teilen
[5][2][8][1] [9][3][7][4]
↓ mergen (sortiert)
[2,5] [1,8] [3,9] [4,7]
↓ mergen
[1, 2, 5, 8] [3, 4, 7, 9]
↓ mergen
[1, 2, 3, 4, 5, 7, 8, 9]
public static void mergeSort(int[] arr, int lo, int hi) {
if (hi - lo <= 1) return;
int mid = (lo + hi) / 2;
mergeSort(arr, lo, mid);
mergeSort(arr, mid, hi);
merge(arr, lo, mid, hi);
}
private static void merge(int[] arr, int lo, int mid, int hi) {
int[] tmp = new int[hi - lo];
int i = lo, j = mid, k = 0;
while (i < mid && j < hi) {
tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
}
while (i < mid) tmp[k++] = arr[i++];
while (j < hi) tmp[k++] = arr[j++];
System.arraycopy(tmp, 0, arr, lo, tmp.length);
}Das Teilen geht Ebenen tief, auf jeder Ebene werden insgesamt Elemente merged:
| Fall | Komplexität |
|---|---|
| Worst Case | |
| Average Case | |
| Best Case |
Mergesort hat garantierte , egal wie die Eingabe aussieht. Das ist der große Vorteil gegenüber Quicksort.
Java's Arrays.sort() für Objekte nutzt eine Mergesort-Variante (Timsort).
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).
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.
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Der simpelste Suchalgorithmus: jedes Element prüfen bis Treffer oder Ende. Funktioniert auf jedem Array, sortiert oder nicht. O(n) im Worst Case.
Lineare und binäre Suche live nebeneinander. Bei welchem n lohnt sich der Aufwand des Sortierens? Wann ist Linear schneller? Klausur-Übersicht.
Was du in der Klausur können musst:
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.
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.
[5, 2, 8, 1, 9, 3, 7, 4]
↓ teilen
[5, 2, 8, 1] [9, 3, 7, 4]
↓ teilen
[5, 2] [8, 1] [9, 3] [7, 4]
↓ teilen
[5][2][8][1] [9][3][7][4]
↓ mergen (sortiert)
[2,5] [1,8] [3,9] [4,7]
↓ mergen
[1, 2, 5, 8] [3, 4, 7, 9]
↓ mergen
[1, 2, 3, 4, 5, 7, 8, 9]
public static void mergeSort(int[] arr, int lo, int hi) {
if (hi - lo <= 1) return;
int mid = (lo + hi) / 2;
mergeSort(arr, lo, mid);
mergeSort(arr, mid, hi);
merge(arr, lo, mid, hi);
}
private static void merge(int[] arr, int lo, int mid, int hi) {
int[] tmp = new int[hi - lo];
int i = lo, j = mid, k = 0;
while (i < mid && j < hi) {
tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
}
while (i < mid) tmp[k++] = arr[i++];
while (j < hi) tmp[k++] = arr[j++];
System.arraycopy(tmp, 0, arr, lo, tmp.length);
}Java: rekursives Splitten plus Merge in einen Hilfsarray. Aufruf: mergeSort(arr, 0, arr.length).
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultPython: funktionaler Stil, gibt sortierte Liste zurück. Slicing ist hier O(n), insgesamt bleibt es O(n log n).
Das Teilen geht log₂ n Ebenen tief, auf jeder Ebene werden insgesamt n Elemente merged:
Aufwand = n · log₂ n = O(n log n)
| Fall | Komplexität |
|---|---|
| Worst Case | O(n log n) |
| Average Case | O(n log n) |
| Best Case | O(n log n) |
Mergesort hat garantierte O(n log n), egal wie die Eingabe aussieht. Das ist der große Vorteil gegenüber Quicksort.
Java's Arrays.sort() für Objekte nutzt eine Mergesort-Variante (Timsort).
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:
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.
Klausurfragen mit Lösungen (6)
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²).
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.
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.
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.
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
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.
Typ: Multi-Select