BPC-ALD - Skripta_rev2019_2

V okamžiku, kdy všechny běhy ze vstupních souborů jsou přečteny, výstupní soubory uzavřeme 
a  otevřeme  je  jako  vstupní  a  předchozí  vstupní  soubory  uzavřeme  a  otevřeme  je  nyní  jako 
výstupní.  A  znovu  opakujeme  proces  zatřiďování.  Tenhle  postup  probíhá  tak  dlouho,  dokud 
vytvořený výstupní běh není tak dlouhý, že obsahuje všechny tříděné prvky. 

Příklad. Budeme třídit prvky 

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

Počet souborů zvolme r=4. Polovina je v=2. 

Ve fázi rozdělování se vytvoří dva soubory s prvky 

1. soubor:   3  5  12 11 17  19  2  9 

2. soubor:   7  15  1  8  4  10  6  14 

Délka běhů je na začátku 1.  

Tyto  soubory  učiníme  vstupní  a  necháme  proběhnout  zatřiďování,  na  jehož  závěru  budou 
vytvořeny dva soubory s běhy délky 2: 

1. soubor:   3  7  |  1  12  |  4  17  |  2  6 

2. soubor:   5  15  |  8  11  |  10  19  |  9  14 

Opět tyto vytvořené soubory otevřeme jako vstupní a necháme na nich proběhnout zatřiďování, 
na jehož závěru budeme mít soubory s běhy délky 4: 

1. soubor:   3  5  7  15  |  4  10  17  19 

2. soubor:   1  8  11  12  |  2  6  9  14 

A znovu úlohu vstupních a výstupních souborů obrátíme a znovu necháme proběhnout proces 
zatřiďování. Nyní vzniknou běhy délky 8: 

1. soubor:   1  3  5  7  8  11  12  15  

2. soubor:   2  4  6  9  10  14  17  19