Der Zeitkomplexität von Merge Sort ist O(n log n) in beiden Durchschnitt Und schlimmste Fälle . Die räumliche Komplexität von Zusammenführen, sortieren Ist An) . 
| Aspekt | Komplexität |
|---|---|
| Zeitkomplexität | O(n log n) |
| Weltraumkomplexität | An) |
Zeitkomplexitätsanalyse der Zusammenführungssortierung:
Betrachten Sie die folgenden Terminologien:
T(k) = Zeit, die zum Sortieren von k Elementen benötigt wird
M(k) = Zeit, die zum Zusammenführen von k Elementen benötigt wird
Es kann also geschrieben werden
T(N) = 2 * T(N/2) + M(N)
= 2 * T(N/2) + Konstante * N
Diese N/2-Elemente werden weiter in zwei Hälften unterteilt. Also,
T(N) = 2 * [2 * T(N/4) + Konstante * N/2] + Konstante * N
= 4 * T(N/4) + 2 * N * Konstante
. . .
= 2k* T(N/2k) + k * N * Konstante
Es kann maximal so lange geteilt werden, bis noch ein Element übrig ist. Also, dann N/2k= 1. k = log 2 N
T(N) = N * T(1) + N * log2N * konstant
= N + N * log2N
Daher ist die Zeitkomplexität O(N * log 2 N) .
Im besten Fall, im schlechtesten Fall und im durchschnittlichen Fall ist die zeitliche Komplexität also gleich.
Raumkomplexitätsanalyse der Zusammenführungssortierung:
Zusammenführen, sortieren hat ein Raumkomplexität von An) . Dies liegt daran, dass ein zusätzliches Größenarray verwendet wird N um die sortierten Hälften des Eingabearrays zusammenzuführen. Das Hilfsarray wird zum Speichern des zusammengeführten Ergebnisses verwendet und das Eingabearray wird mit dem sortierten Ergebnis überschrieben.