Zdaj torej znamo zliti dve urejeni zaporedji v eno daljše urejeno zaporedje. Kako si lahko s tem pomagamo pri urejanju enega samega zaporedja (ki je na začetku neurejeno)? Naše vhodno zaporedje a razbijmo na dva približno enako dolga dela; vsak del posebej uredimo (z enakim postopkom); nato pa tako urejena dela zlijmo v eno zaporedje, ki bo tako postalo urejena različica prvotnega zaporedja a.
Mimogrede, tak pristop, pri katerem problem razbijemo na manjše podprobleme in nato njihove rešitve združimo v rešitev prvotnega problema, pride v računalništvu pogosto prav. Po zgledu iz zgodovine ga imenujemo deli in vladaj (lat. divide et impera).
(a) Dopolni funkcijo ZlijZaporedji
tako, da bo na začetku vsake iteracije izpisala vsebino tabele a od indeksa i naprej, tabele b od indeksa j naprej in celotno tabelo c, podobno kot smo pisali v primeru zgoraj.
(b) Preizkusi jo na nekaj primerih vhodnih zaporedij a in b ter se prepričaj, da deluje pravilno. Ali deluje tudi, če se v vhodnih zaporedjih pojavlja več enakih elementov?
(a) Dopolni funkcijo UrejanjeZZlivanjem
tako, da na začetku izpiše vhodno zaporedje a
, pred vrnitvijo iz funkcije pa izpiše še končno urejeno zaporedje.
(b) Preizkusi jo na nekaj primerih različno dolgih vhodnih zaporedij a in se prepričaj, da deluje pravilno.
(c) Kaj se zgodi, če pozabimo na začetku posebej obravnavati primer, ko je n <= 1
?
(d) Izmeri čas izvajanja funkcije (brez dodatnega izpisa iz točke (a)) na več različno dolgih vhodnih zaporedjih in ga primerjaj s časi, ki si jih izmeril(-a) v prejšnjih razdelkih pri urejanju z izbiranjem in urejanju z vstavljanjem.
(e) Dopolni funkcijo UrejanjeZZlivanjem
tako, da v neki globalni tabeli šteje, kolikokrat je bila poklicana s tabelami neke dolžine. Preizkusi funkcijo na nekem zaporedju, katerega dolžina je potenca števila 2, na primer n = 2 · 2 · 2 · 2 · 2 = 32 in podobno. Opazuj, koliko klicev na kako dolgih tabelah pri tem nastane.