ℹ️ Merge Sort – Erklärung
Idee — Merge Sort teilt das Array rekursiv in zwei gleich große Hälften, bis jede Hälfte nur noch ein Element enthält (trivial sortiert). Anschließend werden die Hälften paarweise zusammengeführt (gemergt), wobei die jeweils kleinsten Elemente verglichen und in Reihenfolge in ein Ausgabe-Array geschrieben werden. Die Puffer-Visualisierung zeigt genau diese Merge-Phase.
Komplexität — Immer O(n log n) für Vergleiche – keine ungünstigen Eingaben möglich. Benötigt O(n) Zusatzspeicher für die Puffer.
Eigenschaften
- Stabil: Ja – gleiche Elemente behalten ihre ursprüngliche Reihenfolge.
- In-place: Nein – O(n) Hilfsspeicher für die Merge-Puffer.
1 / 54
Eingabe-ArrayKlick = bearbeiten · Rechtsklick = löschen
38
27
43
3
9
82
10
+
Start: Array mit 7 Elementen. Merge Sort teilt das Array rekursiv in Hälften und fügt sie sortiert zusammen (Teilen & Herrschen).
↓ Teilen (Divide)—Array rekursiv halbieren bis Einzelelemente
38
27
43
3
9
82
10
38
27
43
3
9
82
10
38
27
43
3
9
82
10
38
27
43
3
9
82
↕ Basis: Einzelelemente sind trivial sortiert
↑ Zusammenführen (Merge)—Sortierte Hälften schrittweise zusammenführen
27
38
3
43
9
82
10
3
27
38
43
9
10
82
3
9
10
27
38
43
82
Aktiver SplitAktives MergeGerade platziertTeilsortiertFertig