Čo je algoritmus zoraďovania zlúčenia [Vysvetlené na príkladoch]

Zlúčiť zoradenie je triediaci algoritmus, ktorý funguje tak, že rekurzívne rozdeľuje pole na menšie a menšie podpole, kým každé podpole neobsahuje iba jeden prvok. Podpolia sa potom zlúčia v zoradenom poradí, počnúc najmenšími podpoliami až po najväčšie podpole.

Tu je príklad, ako funguje zoraďovanie zlúčením. Začnime s nasledujúcim poľom:

```

[5, 3, 1, 2, 4]

```

Najprv rozdelíme pole na dve podpole:

```

[5, 3]

[1, 2, 4]

```

Potom rekurzívne triedime každé podpole. Prvé podpole je už zoradené, takže nemusíme robiť nič. Druhé podpole možno triediť rekurzívnym rozdelením na ďalšie dve podpole atď.

Keď sú podpolia zoradené, môžeme ich zlúčiť v zoradenom poradí. Začneme porovnaním prvých prvkov každého podpolia. Menší prvok sa pridá do zoradeného poľa a druhý prvok sa zahodí. Pokračujeme v tomto procese, kým sa do zoradeného poľa nepridajú všetky prvky v oboch podpoliach.

```

[1, 2, 3, 4, 5]

```

Posledným krokom je vrátenie zoradeného poľa.

Zlúčiť triedenie má množstvo výhod oproti iným triediacim algoritmom. Je zaručené, že vytvorí triedené pole v čase O(n log n) bez ohľadu na počiatočné poradie prvkov v poli. Okrem toho je zoradenie zlúčením stabilné, čo znamená, že prvky, ktoré sú rovnaké, sa objavia v zoradenom poli v rovnakom poradí, ako sa objavili v pôvodnom poli.

Tu je podrobnejšie vysvetlenie algoritmu zoradenia zlúčenia:

1. Rozdeľte pole na dve podpolia približne rovnakej dĺžky.

2. Rekurzívne triediť každé podpole.

3. Zlúčte dve zoradené podpole do jedného zoradeného poľa.

Krok zlúčenia je kľúčom k triedeniu zlúčenia. Je dôležité zlúčiť podpolia v zoradenom poradí. Dá sa to urobiť porovnaním prvých prvkov každého podpola a pridaním menšieho prvku do zoradeného poľa. Ďalší prvok sa vyradí. Tento proces sa opakuje, kým sa do zoradeného poľa nepridajú všetky prvky v oboch podpoliach.

Merge sort je výkonný triediaci algoritmus, ktorý zaručene vytvorí triedené pole v čase O(n log n). Je tiež stabilný, vďaka čomu je vhodný na triedenie údajov, ktoré obsahujú rovnaké prvky.

• Predchádzajúca strana: Čo je Laravel [podrobne vysvetlené] 
• Ďalšia strana: Čo je algoritmus rýchleho triedenia [Vysvetlené na príkladoch]