The Laiko sudėtingumas iš Merge Sort yra O(n log n) abiejuose vidutinis ir blogiausi atvejai . Erdvės sudėtingumas Sujungti rūšiavimą yra O(n) . 
| Aspektas | Sudėtingumas |
|---|---|
| Laiko sudėtingumas | O(n log n) |
| Erdvės sudėtingumas | O(n) |
Sujungimo rūšiavimo laiko sudėtingumo analizė:
Apsvarstykite šiuos terminus:
T(k) = laikas, reikalingas k elementų surūšiavimui
M(k) = laikas, reikalingas k elementų sujungimui
Taigi, galima parašyti
T(N) = 2 * T(N/2) + M(N)
= 2 * T(N/2) + konstanta * N
Šie N/2 elementai dar skirstomi į dvi dalis. Taigi,
T(N) = 2 * [2 * T(N/4) + konstanta * N/2] + konstanta * N
= 4 * T(N/4) + 2 * N * konstanta
. . .
= 2k* T(N/2k) + k * N * konstanta
Jį galima padalyti daugiausia, kol lieka vienas elementas. Taigi, tada N/2k= 1. k = log 2 N
T(N) = N * T(1) + N * log2N * konstanta
= N + N * log2N
Todėl laiko sudėtingumas yra O(N * log 2 N) .
Taigi geriausiu, blogiausiu ir vidutiniu atveju laiko sudėtingumas yra toks pat.
Sujungimo rūšiavimo erdvės sudėtingumo analizė:
Sujungti rūšiavimą turi erdvės sudėtingumas apie O(n) . Taip yra todėl, kad jame naudojamas pagalbinis dydžio masyvas n norėdami sujungti surūšiuotas įvesties masyvo puses. Pagalbinis masyvas naudojamas sujungtam rezultatui saugoti, o įvesties masyvas perrašomas surūšiuotu rezultatu.