Sortiranje polifaznim spajanjem

Sortiranje polifaznim spajanjem (engl. Polyphase merge sort) je algoritam koji smanjuje broj prolaza u svakoj iteraciji u glavnoj petlji spajanjem prolaza u veće prolaze. Koristi se za spoljašnje sortiranje.

Obično sortiranje spajanjem

Tipično, sortiranje spajanjem deli stavke u sortirane prolaze i onda rekurzivno spaja svaki prolaz u vece prolaze. kada postoji samo jos jedan krug, to je sortiran rezultat.

Obično merge sortiranje mogo bi da koristi četiri radne datoteke organizovane kao par ulaznih i par izlaznih datoteka. U svakoj iteraciji, dve ulazne datoteke se čitaju. Neparni numerisani prolazi prve dve ulazne datoteke se spajaju u prvu izlaznu datoteku, a parno numerisani prolazi se spajaju u drugu izlaznu datoteku. Kada je ulaz iscrpljen, novi izlazni fajlovi se koriste kao ulaz u sledeću iteraciju. Broj prolaza je smanjuje za faktor 2 u svakoj iteraciji. U svakoj iteraciji, isotg nivoa/faze spajanja fajl je ili potpuno pročitan ili potpuno napisan tokom iteracije.

Ako su četiri fajla na četiri različite trake/diska , posmatrajući obično merge sortiranje možemo primetiti neke zanimljive detalje.U prvoj iteraciji, koristi se samo jedna ulazna traka—drugi ulazni fajl je prazan. Na narednim iteracijama, svaki ulayni disk radi na pola brzine, dok jedna izlazni disk radi punom brzinom drugi izlazni stoji neaktivan disk i čeka sledeći krug. Situacija je još gora kada se koristi šest diskova, najmanje dva stoje neaktivni.

Polifazni merge pronalazi način da iskoristi neaktivne diskove. Moye da sortira i pomocu tri različite datoteke, u odnosu na četiri koje zahteva običan merge sort.

Polifazno spajanje

Polifazni merge menja igru. Može postojati $N$ fajlova, ali ce polifazni merge čitati iz $N-1$ fajla i pisati samo jedan fajl istovremeno. upisivanje u taj izlazni fajl se nastavlja dok ulazni fajl ne bude iscrpljen,i tada taj ulazni fajl postaje novi izlazni fajl. broj prolaza u svakom fajlu je povezan sa Fibonačijevim brojem i Fibonačijevi brojevi višeg reda.

Savršeno sortiranje polifaznim spajanjem sa tri fajla

Najlakše je gledati na polifazni merge počevši od njegovog završnog stanja i raditi u nazad. Na startu svake iteracije , bice dva ulazna fajla i jedan izlazni fajl. Na kraju iteracije , jedan fajl će biti potpuno istrosšen i on će postati izlazni fajl za sledeću iteraciju. Trenutni izlazni fajl če postati ulazni za sledeču iteraciju. Ostali fajlovi(samo jedan u slucaju 3 fajla) je samo polovično obrađen i ostatak prolaza tog fajla će biti ulaz za sledeđe iteracije.

Fajl jedna je prazan i psotaje novi izlazni fajl. Jedan obilazak je ostao u svakoj ulaznoj traci , a spajanje tih obilazaka če ćiniti sortiran fajl.

File 1 (out):                                           <1 run> *        (the sorted file)
File 2 (in ): ... | <1 run> *               -->     ... <1 run> | *          (consumed)
File 3 (in ):     | <1 run> *                           <1 run> | *          (consumed)

...  mogući obilasci koji su već bili pročitani
|    pokaivač čitanja fajla
*    kraj fajla

Korak nazad na prethodnu iteraciju, čitlai smo iz 1 i 2. Jedan obilazak je spojen iz 1 i 2 pr nego sto fajl 1 postane prazan . Primetiti da fajl 2 nije potpuno obrađen—ostao je jedan obilazak da bi se slagao sa finalnim objedinjavanjem(iznad).

File 1 (in ): ... | <1 run> *                      ... <1 run> | *
File 2 (in ):     | <2 run> *           -->            <1 run> | <1 run> *
File 3 (out):                                          <1 run> *

Koran nazad na prethodnu iteraciju, 2 obilazka su spojena iz 1 i 3 pre nego što fajl 3 psotane prazan.

File 1 (in ):     | <3 run>                        ... <2 run> | <1 run> *
File 2 (out):                               -->        <2 run> *
File 3 (in ): ... | <2 run> *                          <2 run> | *

Korak nazad na prethodnu iteraciju, 3 obilazka su spojena iz 2 i 3, pre nego što fajl 2 postane prazan.

File 1 (out):                                          <3 run> *
File 2 (in ): ... | <3 run> *               -->    ... <3 run> | *
File 3 (in ):     | <5 run> *                          <3 run> | <2 run> *

Korak nazad na prethodnu iteraciju , 5 obilazaka su spojena iz 1 i 2 pre nego što je fajl 1 postane prazan.

File 1 (in ): ... | <5 run> *                      ... <5 run> | *
File 2 (in ):     | <8 run> *               -->        <5 run> | <3 run> *
File 3 (out):                                          <5 run> *

Gledajući brojeve obilazaka u nazad: 1, 1, 2, 3, 5, ... otkriva Fibonačijev niz.

Da bi sve radilo kako treba, početni fajl sortiran mora biti distribuiran na odgovarajuće ulazne fajlove i svaki ulazni fajl mora imati tačan broj obilazaka na tome ... Na primer , to bi značilo da ulazni fajl sa 13 obilazaka će pisati 5 obilazaka u fajl 1 a 8 obilazaka u fajl 2.

U praksi,neće se desiti da ulazni fajl ima Fibonačijev broj obilazaka (i broj obilazaka se neće znati dok fajl ne bude pročitan).

Za poređenje, obično merge sortiranje će kombinovati 16 obilazaka u 4 iteracije koristeći 4 fajla. Polifazni merge će kombinovati 13 obilazaka u 5 iteracija koristeći samo 3 fajla.. Alternativno, polifazni merge če kombinovati 17 obilazaka u 4 iteracije koristeći 4 fajla. (niz: 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, ...)

Iteracija u običnom merge sortiranju uključuje pisanje i čitanje celog fajla. Iteracija u polifaznom merge-u ne čita i ne piše ceo fajl , tako da će trajati kraće od iteracije u običnom merge sortiranju.

Literatura

• Bradley, James (1982). File and Data Base Techniques. Holt, Rinehart and Winston. ISBN 0-03-058673-9. 
• Sedgewick, Robert (1983). Algorithms. Addison-Wesley. стр. 163-165. ISBN 0-201-06672-6.