ℹ️ Merge Sort – Explanation
Idea— Merge Sort recursively splits the array into two halves until each half contains one element (trivially sorted). The halves are then merged in pairs, comparing the smallest elements and writing them in order into an output array. The buffer visualization shows exactly this merge phase.
Complexity — Always O(n log n) comparisons — no bad inputs possible. Requires O(n) extra memory for the buffers.
Properties
- Stable: Yes – equal elements retain their original order.
- In-place: No – O(n) auxiliary memory for the merge buffers.
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