De Tidskomplexitet av Merge Sort är O(n log n) i både genomsnitt och värsta fall . Rymdkomplexiteten av Slå samman sortering är På) . 
| Aspekt | Komplexitet |
|---|---|
| Tidskomplexitet | O(n log n) |
| Rymdkomplexitet | På) |
Tidskomplexitetsanalys av sammanslagningssortering:
Tänk på följande terminologier:
T(k) = tid det tar att sortera k element
M(k) = tiden det tar att slå samman k element
Så det går att skriva
T(N) = 2 * T(N/2) + M(N)
= 2 * T(N/2) + konstant * N
Dessa N/2-element är ytterligare uppdelade i två halvor. Så,
T(N) = 2 * [2 * T(N/4) + konstant * N/2] + konstant * N
= 4 * T(N/4) + 2 * N * konstant
. . .
= 2k* T(N/2k) + k * N * konstant
Den kan maximalt delas tills det finns ett element kvar. Så, då N/2k= 1. k = log 2 N
T(N) = N * T(1) + N * log2N * konstant
= N + N * log2N
Därför är tidskomplexiteten O(N * log 2 N) .
Så i bästa fall, värsta fall och genomsnittsfallet är tidskomplexiteten densamma.
Rymdkomplexitetsanalys av sammanslagningssortering:
Slå samman sortering har en rymdkomplexitet av På) . Detta beror på att den använder en extra array av storlek n för att slå samman de sorterade halvorna av inmatningsmatrisen. Hjälpmatrisen används för att lagra det sammanslagna resultatet, och inmatningsmatrisen skrivs över med det sorterade resultatet.