Zlivanje

Pri urejanju z zlivanjem problem najprej razbijemo na podprobleme velikosti 1, nato pa podprobleme po parih zlivamo v urejeno zaporedje. Vendar se v naravnih podatkih pogosto pojavijo naraščajoča podzaporedja, kar lahko s pridom izkoristimo pri pospešitvi algoritma. Pri naravnem zlivanju v zaporedju najprej poiščemo urejena podzaporedja, kjer si elementi sledijo v nepadajočem vrstnem redu - čete. Nato čete po skupinah združujemo/zlivamo tako, da z začetkov čet zaporedoma pobiramo najmanjše elemente.

Simulirajte algoritem zunanjega urejanja z naravnim k-smernim zlivanjem. Podano je zaporedje z $N$ elementi $x_i$, število čet $K$, ki jih sočasno zlivamo, in število korakov $A$. Določite zaporedje po $A$ korakih. Če je zaporedje urejeno prej kot po $A$ korakih, postopek zaključite.

Omejitve podatkov:

• $1 \leq N \leq 10^6$
• $2 \leq K \leq 10$
• $1 \leq A \leq 20$
• $0 \leq x_i \leq 10^9$

Vhodni in izhodni podatki:

V prvi vrstici so podani število podatkov $N$, število čet $K$, ki jih sočasno zlivamo in število korakov $A$. Sledi $N$ vrstic, kjer $i$-ta vrstica opisuje $i$-ti podatek $x_i$.

V eni vrstici izpišite s presledki ločeno zaporedje po $A$ korakih zlivanja.

Primer vhoda:

25 3 2
13
18
7
8
17
3
16
9
10
11
11
0
2
19
14
5
6
15
4
5
12
3
18
1
3

Pravilen izhod:

0 2 3 3 4 5 5 6 7 8 9 10 11 11 12 13 14 15 16 17 18 18 19 1 3

Komentar:

Postopek za zgornji primer $N=25$, $K=3$ in $A=2$:

V zaporedju na sliki najdemo 10 čet.

V fazi zlivanja nato združujemo po 3 zaporedne čete tako, da zaporedno z začetkov čet izbiramo najmanjše elemente:

Nato nadaljujemo z drugo skupino $K$ čet, ...

dokler nam čet ne zmanjka (zadnja skupina ima lahko manj kot $K$ čet). Po prvem koraku zlivanja, bo zgornje zaporedje izgledalo tako (barve označujejo četo iz katere smo dobili določen element):

V drugem koraku nam ostanejo še štiri čete

na katerih ponovimo postopek zlivanja $K$ zaporednih čet.