Urejanje z zlivanjem

Zlivanje je postopek, s katerim dve naraščajoči zaporedji združimo v novo zaporedje, ki vsebuje vse elemente vhodnih zaporedij in je tudi sámo naraščajoče.

Označimo vhodni zaporedji z a = [a0, a1, ..., an-1] in b = [b0, b1, ..., bm-1]. V izhodnem (združenem) zaporedju, ki ga skušamo zdaj sestaviti, bo moral biti na začetku tisti element, ki je najmanjši izmed vseh elementov v a in b skupaj. Opazimo lahko, da sta za ta element le dve možnosti: a0 in b0. To je posledica dejstva, da sta a in b urejeni; zato so vsi poznejši elementi zaporedja a večji od a0, vsi poznejši elementi zaporedja b pa so večji od b0, torej nobeden od njih ne bo primeren za najmanjši element združenega zaporedja.

Poglejmo torej, kateri od a0 in b0 je manjši, in ga premaknimo od tam na začetek izhodnega zaporedja. Vhodno zaporedje, iz katerega je ta element prišel, je s tem izgubilo svoj prvi element in je zdaj malo krajše kot prej. Zdaj lahko spet primerjamo začetna elementa obeh vhodnih zaporedij, premaknemo manjšega od njiju na konec izhodnega zaporedja in tako naprej, dokler ne premaknemo vseh elementov.

Pri izvedbi tega postopka v praksi moramo paziti še na eno podrobnost. Če imamo zaporedja predstavljena s tabelami, je brisanje prvega elementa tabele ponavadi precej zamudna operacija (ker je treba vse poznejše elemente premakniti za eno mesto nazaj po tabeli). Zato elementov raje ne brišemo, pač pa si v neki spremenljivki zapomnimo, koliko elementov smo iz tistega zaporedja že premaknili v izhodno zaporedje. Če smo recimo iz a-ja premaknili v izhodno zaporedje že i elementov, potem moramo v naslednji primerjavi obravnavati element a[i ] (in ne na primer a[0]).

Oglejmo si konkreten primer. Recimo, da imamo zaporedji: 

a = [5, 6, 8, 10] in b = [1, 3, 7, 9]


Na začetku torej primerjamo 5 (prvi element a-ja) in 1 (prvi element b-ja); ker je 1 manj kot 5, premaknemo 1 iz b-ja v izhodno zaporedje (recimo mu c). Tako dobimo: 

a = [5, 6, 8, 10], b = [3, 7, 9], c = [1]

Zdaj primerjamo 5 (prvi element a-ja) in 3 (prvi element b-ja); 3 je manj kot 5, zato premaknemo 3 iz b v izhodno zaporedje c: 

a = [5, 6, 8, 10], b = [7, 9], c = [1, 3]

V naslednjem koraku primerjamo 5 in 7 ter premaknemo 5 iz a v c: 

a = [6, 8, 10], b = [7, 9], c = [1, 3, 5]

In tako naprej: 

a = [8, 10], b = [7, 9], c = [1, 3, 5, 6]
a = [8, 10], b = [9], c = [1, 3, 5, 6, 7]
a = [10], b = [9], c = [1, 3, 5, 6, 7, 8]
a = [10], b = [], c = [1, 3, 5, 6, 7, 8, 9]

Zdaj se je vhodno zaporedje b že izpraznilo, a pa še ne. To pomeni, da so vsi preostali elementi a-ja večji od vseh elementov, ki so bili kadarkoli v b-ju, zato moramo le še premakniti ta preostanek a-ja na konec izhodnega zaporedja. Tako dobimo združeno urejeno zaporedje: 

c = [1, 3, 5, 6, 7, 8, 9, 10]