Overview
Teilen → Rekursiv sortieren → Zusammenführen; garantiert O(n log n) für alle Eingaben.
Analogy
Zwei sortierte Kartenstapel zusammenführen: immer die kleinste Karte oben nehmen.
Step-by-step
- Teile das Array in der Mitte (mid = len//2).
- Sortiere rekursiv linke und rechte Hälfte.
- Zusammenführen: zwei Zeiger über beide Hälften, jeweils das kleinere Element nehmen.
- Kopiere verbleibende Elemente der nicht-leeren Hälfte.
Visual
[8,3,5,1]: teile→[8,3],[5,1]→sort→[3,8],[1,5]→merge→[1,3,5,8]
Common mistakes
- Vergessen, den Rest einer Hälfte zu kopieren nach dem Zusammenführen.
- In-Place-Merge ist schwierig und langsam – normalerweise Hilfsspeicher verwenden.
Practice questions
- Merge-Sort für verkettete Listen implementieren.
- Bottom-Up iterativen Merge-Sort ohne Rekursion implementieren.
Time
O(n log n) best/average/worst