Urejanje z zlivanjem

Razmislimo še o časovni zahtevnosti tega postopka. Označimo čas urejanja zaporedja n elementov s T(n). Ker naš postopek temelji na razbijanju tabele na dva enaka dela, bo razmislek lažji, če predpostavimo, da je n potenca števila 2; recimo n = 2^k. Pri urejanju tega zaporedja moramo najprej urediti vsako polovico posebej, kar zahteva dve urejanji zaporedij dolžine n/2; pri vsakem od njiju se najprej pojavita dve urejanji zaporedij dolžine n/4, tako da imamo skupaj kar štiri urejanja zaporedij dolžine n/4. Podobno imamo 8 urejanj zaporedij dolžine n/8 in tako naprej; sčasoma pridemo do 2^k urejanj zaporedij dolžine n/2^k, to pa je 1. Za zaporedja dolžine 1 pa smo videli, da naša funkcija z njimi nima nobenega nadaljnjega dela. Tako dobimo naslednjo strukturo klicev:

Poraba časa pri vsakem klicu pa je (če odmislimo čas, ki ga porabimo v njemu podrejenih klicih) premo sorazmerna z dolžino tabele, ki jo pri tistem klicu urejamo (tako razbijanje tabele dolžine m na dve tabeli dolžine m/2 kot zlivanje dveh tabel dolžine m/2 v novo tabelo dolžine m namreč traja O(m) časa). Iz tega sledi, da en klic dolžine n porabi približno enako časa kot dva klica dolžine n/2, pa tudi enako kot štirje klici dolžine n/4 in tako naprej. Vsak nivo klicev torej porabi približno O(n) časa; nivojev pa je k + 1, tako da je časovna zahtevnost približno O(n ⋅ k).

Spomnimo se, da smo k izbrali tako, da je bil n = 2^k. Tak k v matematiki imenujejo (dvojiški) logaritem števila n in ga označijo z log n (ali še bolje log₂ n). Zato tudi pravimo, da ima urejanje z zlivanjem časovno zahtevnost O(n · log n). To je pri večjih n občutno hitreje od O(n²), kar smo videli pri prejšnjih postopkih (urejanje z vstavljanjem in z izbiranjem).

Ima pa tudi urejanje z zlivanjem nekatere slabosti, na primer večjo porabo pomnilnika (za pomožne tabele, kot so levo, desno itd. v naši funkciji UrejanjeZZlivanjem). Za razliko od tega nista urejanje z vstavljanjem in urejanje z izbiranjem porabili nobenega dodatnega pomnilnika, saj sta le premikali elemente po vhodni tabeli a.

Primerjava treh postopkov za urejanje

Simulacija