Time and Space Complexity

Zeitkomplexität:

• Best, Average und Worst Case: O(n log n)
  • Das Array wird etwa log n-mal in der Mitte geteilt, und jede Ebene leistet O(n) Arbeit beim Zusammenführen (Merge). Die Laufzeit hängt nicht von der Reihenfolge der Eingabe ab.

Platzkomplexität:

• O(n)
  • Im Gegensatz zu In-Place-Sortierverfahren erstellt Merge Sort beim Zusammenführen neue Arrays und benötigt daher zusätzlichen Speicher proportional zur Eingabegröße.

Zusammenfassung:

• Merge Sort ist schnell und vorhersehbar: O(n log n) in jedem Fall.
• Es ist stabil, sodass gleiche Elemente ihre Reihenfolge beibehalten.
• Der Nachteil ist der zusätzliche O(n) Speicher, den es für das Zusammenführen verwendet.