Aké rýchle je naše spájanie? Lineárne od počtu prvkov, ktoré spájame.
Poslednou otázkou je časová zložitosť algoritmu. Funkcia merge() zjavne beží v
$O(n)$, každé číslo práve raz presunieme do výsledného poľa.
Predstavme si teraz, čo robí náš algoritmus. Najskôr rozdelí pole na dve polovice
(to je prvá úroveň). Tie rozdelí na dokopy štyri štvrtiny (druhá úroveň) atď.
až kým nedosiahne polia veľkosti $1$. Keďže veľkosti častí na úrovniach
sa stále delia na polovicu, znamená to, že máme približne $\log n$ úrovní.
Otázkou zostáva, koľko práce vykonáme na každej úrovni. Na to si stačí všimnúť, že každý prvok
pôvodného poľa je na každej úrovni zastúpený práve raz,
teda na každej úrovni je $n$ prvkov. Na každej úrovni použijeme niekoľko
volaní lineárneho merge(), ktorým dáme na vstup dokopy $n$ prvkov.
To znamená, že spravíme $O(n)$ operácií. Na $\log n$ úrovniach spravíme $O(n)$
operácii, teda výsledný čas je $O(n \log n)$.
Ešte si ukážeme, ako sa dá zaobísť bez použitia priveľa rôznych pomocných polí. Budeme postupne triediť úseky vstupného poľa. Rozdelenie poľa na dve polovice spravíme ľahko – jednoducho necháme všetky prvky na mieste. Samostatne utriedime prvú polovicu a druhú polovicu poľa. Pomocné pole potrebujeme použiť až v okamihu, kedy ideme obe utriedené polovice spojiť. Vyššie ukázaným postupom ich teda spojíme do pomocného poľa, a následne jeho obsah skopírujeme späť do pôvodného poľa.