Zhrnutie na Triedenie zlučovaním (merge sort)

## Triedenie zlučovaním (Merge Sort) Triedenie zlučovaním, v angličtine známe ako **Merge Sort**, je jeden z najefektívnejších a najčastejšie používaných triediacich algoritmov v informatike. Patrí do kategórie porovnávacích triediacich algoritmov a je založený na princípe „rozdeľ a panuj“ (Divide and Conquer). Bol vynájdený **Johnom von Neumannom v roku 1945**. Jeho hlavnou výhodou je stabilná výkonnosť bez ohľadu na počiatočné usporiadanie vstupných dát, čo z neho robí spoľahlivú voľbu pre triedenie veľkých dátových súborov. > **Rozdeľ a panuj (Divide and Conquer)**: Technika návrhu algoritmov, pri ktorej sa problém rozdelí na dva alebo viacero menších, podobných podproblémov, tieto sa rekurzívne vyriešia a ich riešenia sa nakoniec skombinujú na vyriešenie pôvodného problému. ### Ako Merge Sort funguje? Algoritmus Merge Sort pracuje v dvoch hlavných fázach: 1. **Fáza Rozdeľovania (Divide)**: Pôvodné, netriedené pole sa rekurzívne delí na menšie podpolia, až kým každé podpole neobsahuje len jeden prvok. Jednoprvkové pole je zo svojej podstaty už triedené. 2. **Fáza Zlučovania (Merge)**: Triedené podpolia sa postupne zlučujú do väčších, triedených polí, až kým nezostane len jedno jediné, plne triedené pole. Pri zlučovaní dvoch triedených podpolí sa prvky porovnávajú a umiestňujú do nového, zlúčeného poľa v správnom poradí. ### Príklad Triedenia Zlučovaním Ukážme si krok za krokom, ako Merge Sort triedi pole `[38, 27, 43, 3, 9, 82, 10]`. **Vstup:** `[38, 27, 43, 3, 9, 82, 10]` **1. Fáza Rozdeľovania (Divide):** * Pôvodné pole: `[38, 27, 43, 3, 9, 82, 10]` * Rozdelenie na: `[38, 27, 43, 3]` a `[9, 82, 10]` * `[38, 27, 43, 3]` sa delí na: `[38, 27]` a `[43, 3]` * `[38, 27]` sa delí na: `[38]` a `[27]` (základný prípad – jednoprvkové polia) * `[43, 3]` sa delí na: `[43]` a `[3]` (základný prípad) * `[9, 82, 10]` sa delí na: `[9]` a `[82, 10]` * `[9]` (základný prípad) * `[82, 10]` sa delí na: `[82]` a `[10]` (základný prípad) **2. Fáza Zlučovania (Merge):** Teraz sa začnú zlučovať najmenšie triedené podzoznamy: * Zlúčenie `[38]` a `[27]` $\rightarrow$ `[27, 38]` * Zlúčenie `[43]` a `[3]` $\rightarrow$ `[3, 43]` * Zlúčenie `[82]` a `[10]` $\rightarrow$ `[10, 82]` Ďalšia úroveň zlučovania: * Zlúčenie `[27, 38]` a `[3, 43]` $\rightarrow$ `[3, 27, 38, 43]` * Porovnávame $27$ a $3$. Menšie je $3$. Výsledok: `[3]` * Porovnávame $27$ a $43$. Menšie je $27$. Výsledok: `[3, 27]` * Porovnávame $38$ a $43$. Menšie je $38$. Výsledok: `[3, 27, 38]` * Zostáva $43$. Výsledok: `[3, 27, 38, 43]` * Zlúčenie `[9]` a `[10, 82]` $\rightarrow$ `[9, 10, 82]` * Porovnávame $9$ a $10$. Menšie je $9$. Výsledok: `[9]` * Zostáva `[10, 82]`. Výsledok: `[9, 10, 82]` Posledná úroveň zlučovania: * Zlúčenie `[3, 27, 38, 43]` a `[9, 10, 82]` $\rightarrow$ `[3, 9, 10, 27, 38, 43, 82]` * Porovnávame $3$ a $9$. Menšie je $3$. Výsledok: `[3]` * Porovnávame $27$ a $9$. Menšie je $9$. Výsledok: `[3, 9]` * Porovnávame $27$ a $10$. Menšie je $10$. Výsledok: `[3, 9, 10]` * Porovnávame $27$ a $82$. Menšie je $27$. Výsledok: `[3, 9, 10, 27]` * Porovnávame $38$ a $82$. Menšie je $38$. Výsledok: `[3, 9, 10, 27, 38]` * Porovnávame $43$ a $82$. Menšie je $43$. Výsledok: `[3, 9, 10, 27, 38, 43]` * Zostáva $82$. Výsledok: `[3, 9, 10, 27, 38, 43, 82]` **Výsledok:** `[3, 9, 10, 27, 38, 43, 82]` – triedené pole. ### Bežné chyby a mylné predstavy Pri implementácii alebo pochopení Merge Sortu sa často stretávame s niekoľkými bežnými chybami a nedorozumeniami: 1. **Zabudnutie na základný prípad rekurzie:** Ak sa rekurzia nezastaví pri jednoprvkových (alebo prázdnych) poliach, algoritmus by bežal donekonečna alebo by vyhodil chybu pretečenia zásobníka. 2. **Chyby v logike zlučovania:** Nesprávne porovnávanie prvkov, nesprávne inkrementovanie ukazovateľov alebo zabudnutie skopírovať zostávajúce prvky z jedného z polí po vyčerpaní druhého, vedie