Merge sort opis algorytmu

(wersja z: “Sztuka Programowania”, D.Knuth, tom III)

merge_sort.pas – kod źródłowy

Idea

Najtrudniejszym elementem algorytmu jest scalanie dwóch uporządkowanych ciągów przy użyciu stałej ilości pamięci dodatkowej.

Algorytm:

1. podział scalanego fragmentu na bloki o rozmiarze floor(sqrt(n)), np. dla danych
   
   

   <td id="ca">9</td>
   <td id="ca">13</td>
   <td id="ca">15</td>
   <td id="ca">16</td>
   
   <td id="ca">20</td>
   <td id="ca">25</td>    
   <td id="ca">30</td>
   <td id="cb">0</td>
   
   <td id="cb">2</td>    
   <td id="cb">3</td>
   <td id="cb">6</td>
   <td id="cb">10</td>
   
   <td id="cb">15</td>
   <td id="cb">40</td>
   

   1

   5

   8

   9

   
   bloki mają rozmiar floor(sqrt(18))=4:
   
   

   <td>&nbsp;</td>
   
   <td id="ca">9</td>
   <td id="ca">13</td>
   <td id="ca">15</td>
   <td id="ca">16</td>
   
   <td>&nbsp;</td>
   
   <td id="ca">20</td>
   <td id="ca">25</td>    
   <td id="ca">30</td>
   <td id="cb">0</td>
   
   <td>&nbsp;</td>	
   
   <td id="cb">2</td>    
   <td id="cb">3</td>
   <td id="cb">6</td>
   <td id="cb">10</td>
   
   <td>&nbsp;</td>	
   
   <td id="cb">15</td>
   <td id="cb">40</td>
   

   1

   5

   8

   9

   
   dwa bloki odróżniają się od reszty, pierwszy -- leżący na styku pierwszego i drugiego ciągu (w przykładzie zawiera elementy, 20,25,30,0), i drugi -- ostatni blok w tablicy, który może mieć rozmiar mniejszy niż wszystkie pozostałe.

   
   
   

2. wydzielenia specjalnego fragmentu zwanego buforem pomocniczym (albo "śmietnikiem"), w tym celu należy zamienić miejscami blok zawierający granicę między ciągiami, z ostatnim pełnym blokiem, dla powyższego przykładu byłyby to bloki: (20,25,30,0) i (2,3,6,10)
   
   

   <td>&nbsp;</td>
   
   <td id="ca">9</td>
   <td id="ca">13</td>
   <td id="ca">15</td>
   <td id="ca">16</td>
   
   <td>&nbsp;</td>
   
   <td id="cb">2</td>    
   <td id="cb">3</td>
   <td id="cb">6</td>
   <td id="cb">10</td>
   
   <td>&nbsp;</td>
   
   <td id="swsk">20</td>
   <td id="s">25</td>    
   <td id="s">30</td>
   <td id="s">0</td>	
   
   <td>&nbsp;</td>	
   
   <td id="cb">15</td>
   <td id="cb">40</td>
   

   1

   5

   8

   9

   
   

   (kolorem szarym oznaczony jest bufor pomocniczy, w programie zapamiętywany jest wskaźnik do pierwszego elementu tego bufora t_ptr, na rysunku jest on zaznaczony ciemniejszym kolorem)

   
   
   

3. posortowanie pozostałych bloków (poprzedzających bufor pomocniczy) wg. par (pierwszy element, ostatni element), (tu stosujemy selection-sort, ze względu na małą ilość zamian), ponieważ bloków jest O(sqrt(n)), stąd ten krok zajmie co najwyżej O(n) czasu, dla danych z przykładu tablica miałaby następujący wygląd

   
   
   

   <td>&nbsp;</td>
   
   <td id="cb">2</td>    
   <td id="cb">3</td>
   <td id="cb">6</td>
   <td id="cb">10</td>
   
   <td>&nbsp;</td>
   	
   <td id="ca">9</td>
   <td id="ca">13</td>
   <td id="ca">15</td>
   <td id="ca">16</td>
   
   
   <td>&nbsp;</td>
   
   <td id="swsk">20</td>
   <td id="s">25</td>    
   <td id="s">30</td>
   <td id="s">0</td>	
   
   <td>&nbsp;</td>	
   
   <td id="cb">15</td>
   <td id="cb">40</td>
   

   1

   5

   8

   9

   
   
   

4. scalanie parami bloków (1,2), następnie (2,3), itd, kończąc na parze bloków poprzedzających bufor pomocniczy. Przy scalaniu korzysta się z bufora pomocniczego jako swojego rodzaju pamięci pomocniczej, dokładny opis algorytmu scalania bloków opisany jest w rozdziale "Scalanie bloków". Po wykonaniu wszystkich scaleń otrzymujemy posortowany ciąg. Jednak dalej w buforze pomocniczym i "końcówce" pozostały niescalone elementy.
   
   

   <td>&nbsp;</td>
   
   <td id="cb">6</td>    
   <td id="ca">8</td>
   <td id="ca">9</td>
   <td id="cb">10</td>
   
   <td>&nbsp;</td>
   	
   <td id="ca">9</td>
   <td id="ca">13</td>
   <td id="ca">15</td>
   <td id="ca">16</td>
   
   
   <td>&nbsp;</td>
   
   <td id="swsk">20</td>
   <td id="s">25</td>    
   <td id="s">30</td>
   <td id="s">0</td>	
   
   <td>&nbsp;</td>	
   
   <td id="cb">15</td>
   <td id="cb">40</td>
   
   <td>&nbsp;</td>
   <td id="kom">tablica po scaleniu 1. i 2. bloku</td>
   

   <td>&nbsp;</td>
   
   <td id="cb">6</td>    
   <td id="ca">8</td>
   <td id="ca">9</td>
   <td id="ca">9</td>
   
   <td>&nbsp;</td>
   	
   <td id="cb">10</td>
   <td id="ca">13</td>
   <td id="ca">15</td>
   <td id="ca">16</td>
   
   
   <td>&nbsp;</td>
   
   <td id="swsk">20</td>
   <td id="s">25</td>    
   <td id="s">30</td>
   <td id="s">0</td>	
   
   <td>&nbsp;</td>	
   
   <td id="cb">15</td>
   <td id="cb">40</td>
   
   <td>&nbsp;</td>
   <td id="kom">tablica po scaleniu 2. i 3. bloku</td>
   

   1	2	3	5
   1	2	3	5

   
   
   

5. na nowo należy podzielić tablicę, tym razem na:
   • bufor pomocniczy + resztę drugiego ciągu (niech ma ona rozmiar r),
   • r elementów poprzedzających bufor pomocniczy,
   • pozostałą część tablicy.
   
   Dla danych z przykładu podział miałby następującą postać:
   
   

   <td id="ci">6</td>    
   <td id="ci">8</td>
   
   <td>&nbsp;</td>
   	
   <td id="cj">9</td>
   <td id="cj">9</td>
   
   	
   <td id="cj">10</td>
   <td id="cj">13</td>
   <td id="cj">15</td>
   <td id="cj">16</td>
   
   
   <td>&nbsp;</td>
   
   <td id="ck">20</td>
   <td id="ck">25</td>    
   <td id="ck">30</td>
   <td id="ck">0</td>	
      
   <td id="ck">15</td>
   <td id="ck">40</td>
   

   1

   2

   3

   5

   
   (ponieważ powyższy przykład zawiera stosunkowo niewiele elementów, proporcje między częściami mogą wydawać się nieco zachwiane, druga i trzecia część mają rozmiar co najwyżej 2*sqrt(n), natomiast pierwsza część (dla odpowiednio dużych n) jest największa i ma rozmiar rzędu O(n) (dokładnie n-2r))

   
   
   

6. posortowanie (insertionsort) drugiej i trzeciej części, w sumie mają one rozmiar nie większy niż 4*sqrt(n), stąd koszt takiej operacji wyniesie O(n). Po tej operacji przykładowa tablica miałaby następujący wygląd:
   
   

   <td id="ci">6</td>    
   <td id="ci">8</td>
   
   <td>&nbsp;</td>
   
   <td id="ck">0</td>		
   <td id="cj">9</td>
   <td id="cj">9</td>
   	
   <td id="cj">10</td>
   <td id="cj">13</td>
   <td id="cj">15</td>
   
   <td>&nbsp;</td>
   <td id="ck">15</td>
   
   <td id="cj">16</td>
   
   <td id="ck">20</td>
   <td id="ck">25</td>    
   <td id="ck">30</td>
      
   <td id="ck">40</td>
   

   1

   2

   3

   5

   
   
   

7. scalanie pierwszej i drugiej części, traktując część trzecią jako bufor pomocniczy, zastosowany sposób jest analogiczny do poprzedniego scalania bloków, szerszy opis można znaleźć w rodziale "Scalanie końcówki". Po scaleniu przykładowa tablica miałby następującą postać:
   
   

   <td id="ci">6</td>    
   
   <td>&nbsp;</td>
   
   <td id="ci">8</td>
   
   <td id="cj">9</td>
   <td id="cj">9</td>
   	
   <td id="cj">10</td>
   <td id="cj">13</td>
   <td id="cj">15</td>
   
   <td>&nbsp;</td>
   <td id="ck">15</td>
   
   <td id="cj">16</td>
   
   <td id="ck">20</td>
   <td id="ck">25</td>    
   <td id="ck">30</td>
      
   <td id="ck">40</td>
   

   0

   1

   2

   3

   5

   
   
   

8. w trakcie scalania część trzecia mogła zostać zaburzona (jej elementy zostały wymieszane), stąd konieczne jest jej ponowne posortowanie (insertionsort). Tablica jest już scalona!

Scalanie bloków

Przy scalaniu dwóch bloków o rozmiarze “bsize” korzystamy ze “śmietnika” jako bufora pomocniczego.

Pierwszym krokiem jest zamienienie pierwszego bloku ze śmietnikiem. Następnie idąc od lewej do prawej zaczynamy wypełniać tablice prawidłowymi wartościami (za każdym razem wybieramy z ciągów A i B element o mniejszej wartości i zamieniamy go z pierwszym “wolnym” (tzn. zawierającym element “śmietnikowy”) elementem tablicy. Warto zauważyć, ze za każdym razem gdy zamieniamy z elementem z ciągu A, element “śmietnikowy” wraca juz na swoje miejsce, gdy wybieramy element z B, obszar z elementami “śmietnikowymi” przesuwa się o jedno miejsce w prawo. Powyższe postępowanie kontynuujemy, aż do momenty wyczerpania wszystkich elementów z A i B. Po zakończeniu działania algorytmu wszystkie elementy “śmietnikowe” wróciły na swoje miejsce (ponieważ zamieniliśmy wszystkie elementy z A), mogą jednak zmienić swoja kolejność (tak to np. stało się w przykładzie)

Przykład:

Legenda

Scalanie końcówki

Scalanie końcówki tablicy wykonujemy w analogiczny sposób, co poprzednie scalenia, z dwiema małymi różnicami:

• w pierwszym kroku zamieniamy drugą część z buforem pomocniczym
• tym razem scalone elementy zapisujemy w odwrotnej kolejności, tzn. idąc od lewej do prawej,

Przykład:

Stabilność sortownia

Powyższa metoda nie spełnia założenia o stabilności sortowania, jednak istnieje modyfikacja alg. merge (niestety bardziej skomplikowana) która również działa w miejscu i czasie O(N).