Triedenie zlučovaním

Algoritmy a programovanie

---

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

>Triedenie výmenou
>Triedenie vkladaním
>Triedenie zlučovaním
>Triedenie delením
>Triedenie výberom
>Triedenie - ostatné princípy

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Zlučovací algoritmus Merge

Vizualizácia funkcie Merge: Máme pole prvkov p = [1, 3, 5, 2, 4, 6], ktoré je už čiastočne utriedené. Použijeme algoritmus Merge, ktorý si vytvorí pomocné polia L = [1, 3, 5] a P = [2, 4, 6]. Všetky polia indexujeme od 0, pričom pre pole p používame index k, pre L index i a pre P index j. Postupnosť krokov je označená číslicami 1 až 6.

Princíp zlučovania tkvie v tom, že máme dva alebo viac utriedených zoznamov, ktoré skombinuje do jedného utriedeného zoznamu (výsledný zoznam musí obsahovať všetky prvky z pôvodných zoznamov). Zoznam môže byť reprezentovaný ako dátová štruktúra pole alebo aj ako lineárny zoznam. V tomto článku sa zameriame na algoritmus pre dátovú štruktúru pole.

Algoritmus Merge tvorí kľúčovú časť triediaceho algoritmu MergeSort.

Slovný opis algoritmu

Nech máme pole, ktoré sa skladá z dvoch už utriedených polovíc. Vytvoríme si dve pomocné polia L a P a do každého z nich skopírujeme obsah jednej polovice (L - ľavá polovica, P - pravá polovica). Potom súčasne prechádzame polia L a P od začiatku po koniec, pričom v každom cykle porovnáme prvok poľa L s prvkom v poli P. Z tejto dvojice následne vyberieme minimum, (keď triedime od najmenšieho po najväčší) ktoré vložíme na prvú voľnú pozíciu pôvodného poľa (na začiatku je to prvá pozícia poľa). Nakoniec zvýšime index pri vstupnom poli a pri pomocnom poli, z ktorého vyberáme daný prvok. Túto postupnosť krokov opakujeme, pokiaľ neprídeme na koniec jedného z polí P a L. Ak nastane situácia, že prídeme na koniec jedného z pomocných polí (a v druhom nám ostali ešte nejaké prvky), potom už iba naspäť skopírujeme zbytok druhého pomocného poľa na koniec pôvodného poľa.

Vlastnosti algoritmu

• vhodný pre dátové štruktúry: pole, lineárny zoznam
• časová náročnosť: vždy lineárna [math]O(n)[/math]
• priestorová náročnosť: lineárna [math]O(n)[/math] pre pole (alokovanie pomocných polí), [math]O(1)[/math] pre lineárny zoznam (pri lineárnom zozname netreba alokovať dočasné polia, stačí iba presmerovať smerníky)
• využitie: kľúčový podprogram pre triediaci algoritmus MergeSort

Pseudokód

Nech funkcia Merge má nasledovný prototyp: Merge(pole[], lavy, stred, pravy)

1. Je lavy >= pravy ? Ak áno, skonči, inak pokračuj krokom 2.

2. Nech: i = 0, j = 0, k = lavy

3. Nech: dlzka_L = stred - lavy + 1, dlzka_P = pravy - stred

4. Nech: L = pole[lavy ... stred], P = pole[stred + 1 ... pravy]

5. Je i < dlzka_L a zároveň j < dlzka_P ? Ak áno, pokračuj krokom 5.1., inak skoč na krok 6.

5.1. Je L[i] <= P[j]?

Ak áno:

5.1.1. pole[k] = L[i]

5.1.2. k += 1

5.1.3. i += 1

5.1.4. Skoč na krok 5.

Ak nie:

5.1.1. pole[k] = P[j]

5.1.2. k += 1

5.1.3. j += 1

5.1.4. Skoč na krok 5.

6. Je i < dlzka_L ? Ak áno, pokračuj krokom 6.1., inak skoč na krok 7.

6.1. pole[k] = L[i]

6.2. k += 1

6.3. i += 1

6.4. Skoč na krok 6.

7. Je j < dlzka_P ? Ak áno, pokračuj krokom 7.1., inak skonči.

7.1. pole[k] = P[j]

7.2. k += 1

7.3. j += 1

7.4. Skoč na krok 7.

MergeSort

MergeSort je triediaci algoritmus, ktorý využíva stratégiu "rozdeľuj a panuj", čo znamená, že vstupný zoznam najskôr rozdelí na dve polovice, tie zoradí a potom ich zlúči naspäť dokopy. Radí sa medzi najpoužívanejšie a najviac rešpektované triediace algoritmy.

Vlastnosti algoritmu Merge Sort

• vhodný pre dátové štruktúry: pole, lineárny zoznam
• časová náročnosť: vždy linearitmická [math] O(n.log(n)) [/math], vďaka ktorej dokáže efektívne triediť veľmi veľké zoznamy
• priestorová náročnosť: lineárna [math]O(n)[/math] pre pole (alokovanie dočasných polí), konštantná [math]O(1)[/math] pre lineárny zoznam (pri lineárnom zozname stačí iba presmerovať smerníky)
• druh triedenia: triedenie zlučovaním (komparačný algoritmus)
• stabilita triedenia: stabilný
• miesto triedenia: externé triedenie (vhodný na triedenie veľkých objemov dát uložených na disku)

Z hľadiska implementácie môžeme vytvoriť dve základné verzie algoritmu, a to rekurzívnu a iteračnú.

Opis rekurzívnej a iteračnej verzie algoritmu Merge Sort

Rekurzívna verziaIteračná verzia

Vizualizácia rekurzívnej verzie algoritmu MergeSort

Princíp algoritmu

Algoritmus MergeSort vykonáva 4 základné úlohy:

1. Delenie poľa na dve polovice.
2. Triedenie ľavej polovice poľa.
3. Triedenie pravej polovice poľa.
4. Zlúčenie oboch polovíc pomocou funkcie Merge.

Slovný opis

Našou úlohou je vzostupne (min -> max) utriediť vstupné pole. Určíme si stred poľa (pri párnom počte prvkov je to ten menší z prostredných indexov). Následne vykonávame sériu rekurzívnych delení pre ľavú a pravú časť poľa (začiatok ... stred ; stred + 1 ... koniec) až do momentu, keď nám ostanú len jednoprvkové podpolia (tie sú už utriedené). Následne v každom volaní obe tieto podpolia zlúčime pomocou algoritmu Merge do väčších podpolí (2, 4, 8, ...), až nakoniec dostaneme jedno výsledné utriedené pole.

Pseudokód

Nech nech má funkcia MergeSort nasledovný prototyp: MergeSort(pole[], lavy, pravy)

1. Je lavy >= pravy ? Ak áno, skonči volanie, inak pokračuj krokom 2.

2. Nech: stred = lavy + (pravy - lavy) / 2, pričom znak / vyjadruje celočíselné delenie.

3. Rekurzívne zavolaj funkciu MergeSort(pole[], lavy , stred)

3. Rekurzívne zavolaj funkciu MergeSort(pole[], stred + 1 , pravy)

4. Zavolaj funkciu Merge(pole[], lavy, stred, pravy)

5. Skonči volanie.

Princíp algoritmu

Algoritmus MergeSort vykonáva 3 základné úlohy:

1. Vonkajší cyklus: určenie veľkosti zoznamu na zlučovanie.
2. Vnútorný cyklus: prechádzanie jednotlivých zoznamov v poli.
3. Zlučovanie jednotlivých zoznamov pomocou funkcie Merge.

Slovný opis

Vstupné pole, ktoré má N prvkov, môžeme chápať, ako N rôznych jednoprvkových (utriedených) podpolí, ktoré máme zlúčiť do jedného výsledného N-prvkového utriedeného poľa. Keďže by bolo veľmi nepraktické zlučovať N podpolí naraz, zvolíme nasledovnú stratégiu: Budeme prechádzať dané pole od začiatku po koniec a v prvom cykle zlúčime každé dva prvky, takže budeme mať [math]\frac{n}{2}[/math] dvojprvkových utriedených podpolí. Potom v druhom cykle zlúčime každé 4 prvky do jedného podpoľa, v treťom cykle každých 8, až do momentu, keď dostaneme jedno utriedené pole. Aby sme to docielili, potrebujeme dva cykly, vonkajší, ktorý nastaví maximálnu veľkosť podpoľa, ktoré ideme zlučovať (1,2,4,8 ... dlzka - 1) a vnútorný, ktorý prechádza jednotlivé podpolia. Následne už iba voláme funkciu Merge, ktorá dané podpolia zlučuje.

Poznámka, ak máme pole, ktoré má nepárny počet prvkov, tak ten posledný prvok nezlúčime hneď v prvom cykle, ale až v tých ďalších. Takisto, ak N nie je mocnina čísla 2, tak musíme samozrejme ošetriť situáciu, kedy by sme sa dostali mimo rozsah poľa (Ak máme napríklad pole, čo má 7 prvkov, tak po prvej iterácii budú prvky utiredené podľa vzoru 2 + 2 + 2 + 1, po druhej 4 + 3, a po tretej 7)

Pseudokód

Nech nech má funkcia MergeSort nasledovný prototyp: MergeSort(pole[], lavy, pravy)

1. Je lavy >= pravy ? Ak áno, skonči, inak pokračuj krokom 2.

2. Nech: dlzka_subzoznamu = 1

3. Nech: zaciatok = lavy

4. Jedlzka_subzoznamu <= pravy ? Ak áno pokračuj krokom 4.1, inak skonči.

4.1. Jezaciatok < pravy Ak áno pokračuj krokom 4.1.1, inak skoč na krok 4.2.

4.1.1. Je zaciatok + 2 * dlzka_zoznamu - 1 <= pravy ?

Ak áno:

4.1.1.1. Nech koniec = zaciatok + 2 * dlzka_zoznamu - 1

Ak nie:

4.1.1.1. Nech koniec = pravy

4.1.2. Je zaciatok + dlzka_zoznamu - 1 <= pravy ?

Ak áno:

4.1.2.1. Nech stred = zaciatok + dlzka_zoznamu - 1

Ak nie:

4.1.2.1. Nech stred = pravy

4.1.3. Merge(pole[], zaciatok, stred, koniec)

4.1.4. zaciatok += 2 * dlzka_subzoznamu

4.1.5. Skoč na krok 4.1.

4.2. dlzka_subzoznamu *= 2

4.3 Skoč na krok 4.

Implementácia algoritmov Merge a MergeSort
v rôznych programovacích jazykoch

Rekurzívna: CIteračná: CRekurzívna: C++Iteračná: C++Rekurzívna: JavaIteračná: JavaRekurzívna: Python3Iteračná: Python3

#include <stdio.h>
#include <stdlib.h>

void Merge(int pole[], int lavy, int stred, int pravy);
void MergeSort(int pole[], int lavy, int pravy);

/* hlavný program */

int main()
{
    int pole[] = {12, 11, 13, 5, 6, 7};
    int dlzka_pola = sizeof(pole) / sizeof(pole[0]);

    printf("Pôvodné pole: \n");

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }

    MergeSort(pole, 0, dlzka_pola - 1);

    printf("\nUtriedené pole: \n");

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }
    
    return 0;
}

void Merge(int pole[], int lavy, int stred, int pravy)
{
   /* ak má pole menej ako 2 prvky, skonči */

    if (lavy >= pravy)
    {
        return;
    }

   /* vyrátaj dĺžky oboch polovíc poľa */

   int L_dlzka = stred - lavy + 1;
   int P_dlzka = pravy - stred;

   /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */

   int *L = (int*)malloc(L_dlzka * sizeof(int));
   int *P = (int*)malloc(P_dlzka * sizeof(int));

   /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */

   int i, j, k;

   /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */

   for (i = 0; i < L_dlzka; ++i)
   {
       L[i] = pole[lavy + i];
   }

   for (j = 0; j < P_dlzka; ++j)
   {
       P[j] = pole[stred + 1 + j];
   }

   /* nastav indexy na začiatok daných polí */

   i = 0; j = 0; k = lavy;

  /* zlučuj dočasné polia L a P do finálneho poľa pole */

   while(i < L_dlzka && j < P_dlzka)
   {
       if(L[i] <= P[j])
       {
           pole[k++] = L[i++];
       }
       else
       {
           pole[k++] = P[j++];
       }
   }

   /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */

   while(i < L_dlzka)
   {
       pole[k++] = L[i++];
   }

   /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */

   while(j < P_dlzka)
   {
       pole[k++] = P[j++];
   }

   /* uvoľni použitú pamäť */

   free(L);
   free(P);
}

void MergeSort(int pole[], int lavy, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči volanie */

    if(lavy >= pravy)
    {
        return;
    }
    /* urči si prostredný index */

    int stred = lavy + (pravy - lavy) / 2;

    /* utrieď ľavú polovicu poľa */

    MergeSort(pole, lavy, stred);

    /* utrieď pravú polovicu poľa */

    MergeSort(pole, stred+1, pravy);

    /* zlúč obe polovice dokopy */

    Merge(pole, lavy, stred, pravy);
}

#include <stdio.h>
#include <stdlib.h>

void Merge(int pole[], int lavy, int stred, int pravy);
void MergeSortIt(int *pole, int lavy, int pravy);

/* hlavný program */

int main()
{
    int pole[] = {12, 11, 13, 5, 6, 7, 19};
    int dlzka_pola = sizeof(pole) / sizeof(pole[0]);

    printf("Pôvodné pole %d: \n", dlzka_pola);

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }

    MergeSortIt(pole, 0, dlzka_pola - 1);

    printf("\nUtriedené pole: \n");

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }

    return 0;
}

void Merge(int pole[], int lavy, int stred, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči */

    if (lavy >= pravy)
    {
        return;
    }

    /* vyrátaj dĺžky oboch polovíc poľa */

    int L_dlzka = stred - lavy + 1;
    int P_dlzka = pravy - stred;

    /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */

    int *L = (int*)malloc(L_dlzka * sizeof(int));
    int *P = (int*)malloc(P_dlzka * sizeof(int));

    /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */

    int i, j, k;

    /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */

    for (i = 0; i < L_dlzka; ++i)
    {
        L[i] = pole[lavy + i];
    }

    for (j = 0; j < P_dlzka; ++j)
    {
        P[j] = pole[stred + 1 + j];
    }

    /* nastav indexy na začiatok daných polí */

    i = 0; j = 0; k = lavy;

    /* zlučuj dočasné polia L a P do finálneho poľa pole */

    while(i < L_dlzka && j < P_dlzka)
    {
        if(L[i] <= P[j])
        {
            pole[k++] = L[i++];
        }
        else
        {
            pole[k++] = P[j++];
        }
    }

    /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */

    while(i < L_dlzka)
    {
        pole[k++] = L[i++];
    }

    /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */

    while(j < P_dlzka)
    {
        pole[k++] = P[j++];
    }

    /* uvoľni použitú pamäť */

    free(L);
    free(P);
}

void MergeSortIt(int *pole, int lavy, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči volanie */

    if(lavy >= pravy)
    {
        return;
    }

    int stred, koniec;

    for (int dlzka_zoznamu = 1; dlzka_zoznamu <= pravy ; dlzka_zoznamu *= 2)
    {
        for (int zaciatok = lavy; zaciatok < pravy ; zaciatok += 2 * dlzka_zoznamu)
        {
             koniec = (zaciatok + 2 * dlzka_zoznamu - 1 <= pravy) ? zaciatok + 2 * dlzka_zoznamu - 1 : pravy;

             stred = (zaciatok + dlzka_zoznamu - 1 <= pravy) ? zaciatok + dlzka_zoznamu - 1 : pravy;

             Merge(pole, zaciatok, stred, koniec);

        }
    }
}

#include <iostream>

using std::cout;
using std::endl;

void Merge(int pole[], int lavy, int stred, int pravy);
void MergeSort(int pole[], int lavy, int pravy);

/* hlavný program */

int main()
{
    int pole[] = {12, 11, 13, 5, 6, 7};
    int dlzka_pola = sizeof(pole) / sizeof(pole[0]);

    printf("Pôvodné pole: \n");

    for (auto i: pole)
    {
        cout<<i<<" ";
    }

    MergeSort(pole, 0, dlzka_pola - 1);

    cout<<endl<<"Utriedené pole:"<<endl;

    for (auto i: pole)
    {
        cout<<i<<" ";
    }

    return 0;
}

void Merge(int pole[], int lavy, int stred, int pravy)
{
   /* ak má pole menej ako 2 prvky, skonči */

    if (lavy >= pravy)
    {
        return;
    }

   /* vyrátaj dĺžky oboch polovíc poľa */

   int L_dlzka = stred - lavy + 1;
   int P_dlzka = pravy - stred;

   /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */

   int *L = new int[L_dlzka];
   int *P = new int[P_dlzka];

   /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */

   int i, j, k;

   /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */

   for (i = 0; i < L_dlzka; ++i)
   {
       L[i] = pole[lavy + i];
   }

   for (j = 0; j < P_dlzka; ++j)
   {
       P[j] = pole[stred + 1 + j];
   }

   /* nastav indexy na začiatok daných polí */

   i = 0; j = 0; k = lavy;

  /* zlučuj dočasné polia L a P do finálneho poľa pole */

   while(i < L_dlzka && j < P_dlzka)
   {
       if(L[i] <= P[j])
       {
           pole[k++] = L[i++];
       }
       else
       {
           pole[k++] = P[j++];
       }
   }

   /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */

   while(i < L_dlzka)
   {
       pole[k++] = L[i++];
   }

   /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */

   while(j < P_dlzka)
   {
       pole[k++] = P[j++];
   }

   /* uvoľni použitú pamäť */

   delete []L;
   delete []P;
}

void MergeSort(int pole[], int lavy, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči volanie */

    if(lavy >= pravy)
    {
        return;
    }
    /* urči si prostredný index */

    int stred = lavy + (pravy - lavy) / 2;

    /* utrieď ľavú polovicu poľa */

    MergeSort(pole, lavy, stred);

    /* utrieď pravú polovicu poľa */

    MergeSort(pole, stred+1, pravy);

    /* zlúč obe polovice dokopy */

    Merge(pole, lavy, stred, pravy);
}

#include <iostream>

using std::cout;
using std::endl;

void Merge(int pole[], int lavy, int stred, int pravy);
void MergeSort(int pole[], int lavy, int pravy);

/* hlavný program */

int main()
{
    int pole[] = {12, 11, 13, 5, 6, 7};
    int dlzka_pola = sizeof(pole) / sizeof(pole[0]);

    printf("Pôvodné pole: \n");

    for (auto i: pole)
    {
        cout<<i<<" ";
    }

    MergeSort(pole, 0, dlzka_pola - 1);

    cout<<endl<<"Utriedené pole:"<<endl;

    for (auto i: pole)
    {
        cout<<i<<" ";
    }

    return 0;
}

void Merge(int pole[], int lavy, int stred, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči */

    if (lavy >= pravy)
    {
        return;
    }

    /* vyrátaj dĺžky oboch polovíc poľa */

    int L_dlzka = stred - lavy + 1;
    int P_dlzka = pravy - stred;

    /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */

    int *L = new int[L_dlzka];
    int *P = new int[P_dlzka];

    /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */

    int i, j, k;

    /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */

    for (i = 0; i < L_dlzka; ++i)
    {
        L[i] = pole[lavy + i];
    }

    for (j = 0; j < P_dlzka; ++j)
    {
        P[j] = pole[stred + 1 + j];
    }

    /* nastav indexy na začiatok daných polí */

    i = 0; j = 0; k = lavy;

    /* zlučuj dočasné polia L a P do finálneho poľa pole */

    while(i < L_dlzka && j < P_dlzka)
    {
        if(L[i] <= P[j])
        {
            pole[k++] = L[i++];
        }
        else
        {
            pole[k++] = P[j++];
        }
    }

    /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */

    while(i < L_dlzka)
    {
        pole[k++] = L[i++];
    }

    /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */

    while(j < P_dlzka)
    {
        pole[k++] = P[j++];
    }

    /* uvoľni použitú pamäť */

    delete []L;
    delete []P;
}

void MergeSort(int *pole, int lavy, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči volanie */

    if(lavy >= pravy)
    {
        return;
    }

    int stred, koniec;

    for (int dlzka_zoznamu = 1; dlzka_zoznamu <= pravy; dlzka_zoznamu *= 2)
    {
        for (int zaciatok = lavy; zaciatok < pravy; zaciatok += 2 * dlzka_zoznamu)
        {
            koniec = (zaciatok + 2 * dlzka_zoznamu - 1 <= pravy) ? zaciatok + 2 * dlzka_zoznamu - 1 : pravy;

            stred = (zaciatok + dlzka_zoznamu - 1 <= pravy) ? zaciatok + dlzka_zoznamu - 1 : pravy;

            Merge(pole, zaciatok, stred, koniec);
        }
    }
}

class MergeSort 
{

    /* Funkcia zlúči 2 podpolia, ktoré sme vytvorili z pôvodného poľa.
     * Každé podpole má polovičnú dĺžku pôvodného poľa.
     * subpole1 [ľavý ... stred]
     * subpole2 [stred + 1 ... pravý] 
     */

    void merge(int[] pole, int lavy, int stred, int pravy) 
    {

        // Výpočet dĺžky 2 podpolí

        int n1 = stred - lavy + 1;
        int n2 = pravy - stred;

        // Vytvorenie pomocných polí

        int[] L = new int[n1];
        int[] P = new int[n2];

        // Načítanie dát do pomocných polí

        for (int i = 0; i < n1; i++)
            L[i] = pole[lavy + i];

        for (int j = 0; j < n2; j++)
            P[j] = pole[stred + 1 + j];

        // Počiatočné indexy prvého a druhého podpoľa

        int i = 0, j = 0;

        // Počiatočný index zlúčeného podpoľa

        int k = lavy;

        // Zlúčenie dvoch podpolí

        while (i < n1 && j < n2)
        {
            if (L[i] <= P[j]) 
            {
                pole[k] = L[i];
                i++;
            }
            else 
            {
                pole[k] = P[j];
                j++;
            }
            k++;
        }

        /* V prípade, že sa v jednom zo podpoli nachádzajú ešte nejaké prvky, ktoré neboli zlúčené do pola,
         * tak sa do pola jednoducho skopírujú 
         */

        while (i < n1) 
        {
            pole[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) 
        {
            pole[k] = P[j];
            k++;
            j++;
        }

    }

    /* Funkcia, ktorá zoradí pole použitím funkcie merge() */

    void sort (int[] pole, int lavy, int pravy) 
    {
        if (lavy < pravy) 
        {
            // Musíme nájsť stred pola

            int stred = lavy + (pravy - lavy) / 2;

            // Zoradíme prvú a druhú polovicu pola samostatne

            sort(pole, lavy, stred);
            sort(pole, stred + 1, pravy);

            // Zlúčime zoradené polovice do jedného pola

            merge(pole, lavy, stred, pravy);
        }
    }
}

public class Main
{
    /* Funkcia na výpis pola dĺžky n */

    static void vypis_pole(int[] pole) 
    {
        
        for (int j : pole) 
        {
            System.out.print(j + " ");
        }

        System.out.println();
    }

    /* Hlavný program */

    public static void main(String[] args) 
    {
        int[] pole = {12, 11, 13, 5, 6, 7};

        System.out.println("Zadané pole:");
        vypis_pole(pole);

        MergeSort ms = new MergeSort();
        ms.sort(pole, 0, pole.length - 1);

        System.out.println("\nZoradené pole:");
        vypis_pole(pole);
    }
}

class MergeSort_iteracia 
{
    /* Zlúči 2 subpolia, ktoré sa vytvorili z pôvodného pola.
     * Každé subpole má polovičnú dĺžku pôvodného pola.
     * subpole1 [ľavý..stred]
     * subpole2 [stred+1..pravý] 
     */

    void merge(int[] pole, int lavy, int stred, int pravy) 
    {
        // Výpočet dĺžky 2 subpolí

        int n1 = stred - lavy + 1;
        int n2 = pravy - stred;

        // Vytvorenie pomocných polí

        int[] L = new int[n1];
        int[] P = new int[n2];

        // Načítanie dát do pomocných polí

        for (int i = 0; i < n1; i++)
            L[i] = pole[lavy + i];

        for (int j = 0; j < n2; j++)
            P[j] = pole[stred + 1 + j];

        // Počiatočné indexy prvého a druhého subpola

        int i = 0, j = 0;

        // Počiatočný index zlúčeného subpola

        int k = lavy;

        // Zlúčenie dvoch podpolí

        while (i < n1 && j < n2) 
        {
            if (L[i] <= P[j])
            {
                pole[k] = L[i];
                i++;
            }
            else 
            {
                pole[k] = P[j];
                j++;
            }
            k++;
        }

        /* V prípade, že v jednom zo subpolí sa nachádzajú prvky, ktoré neboli zlúčené do pola,
         * tak sa do pola jednoducho skopírujú 
         */

        while (i < n1) 
        {
            pole[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) 
        {
            pole[k] = P[j];
            k++;
            j++;
        }
    }

    /* Funkcia, ktorá zoradí pole použitím funkcie merge() */

    void sort (int[] pole, int n) 
    {
        /* Dĺžka subpolí, ktoré majú byť zlúčené, hodnoty premennej sa pohybujú v intervale <1;n-1> */

        int aktual_dlzka;

        /* Začiatočný index ľavého subpola, ktoré má byť zlúčené */

        int zaciatok_vlavo;

        /* Vzostupné usporiadanie prvkov. Najskôr sa zlúčia subpolia veľkosti 1 do subpolí veľkosti 2,
        * potom subpolia veľkosti 2 do subpolí veľkosti 4 a tak ďalej 
        */

        for (aktual_dlzka = 1; aktual_dlzka <= n - 1; aktual_dlzka *= 2) 
        {
            /* Určenie začiatočného prvku rôznych subpolí aktuálnej dĺžky subpola */

            for (zaciatok_vlavo = 0; zaciatok_vlavo < n - 1; zaciatok_vlavo += 2 * aktual_dlzka) 
            {
                /* Nájdenie konečného prvku ľavého subpola, stred+1 je začiatočný prvok pravého subpola */

                int stred = Math.min(zaciatok_vlavo + aktual_dlzka - 1, n - 1);
                int koniec_vpravo = Math.min(zaciatok_vlavo + 2 * aktual_dlzka - 1, n - 1);

                /* Zlúči subpolia L[zaciatok_vlavo .. stred] & P[stred+1 .. koniec_vpravo] */

                merge(pole, zaciatok_vlavo, stred, koniec_vpravo);
            }
        }
    }
}

public class Main {

    /* Funkcia na výpis pola dĺžky n */

    static void vypis_pole(int[] pole) 
    {
        int n = pole.length;

        for (int j : pole) 
        {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    /* Hlavný program */

    public static void main(String[] args) {


        /* Inicializácia pola */

        int[] pole = {12, 11, 13, 5, 6, 7};

        System.out.println("Zadané pole:");
        vypis_pole(pole);

        MergeSort_iteracia ms_it = new MergeSort_iteracia();
        ms_it.sort(pole, pole.length);

        System.out.println("Zoradené pole:");
        vypis_pole(pole);
    }
}

def MergeSort(pole):
    if len(pole) > 1:

        # Nájdenie stredu pola
        # zápis len(pole)//2 znamená, že dĺžka pola sa vydelí 2 a výsledok je celé číslo

        stred = len(pole) // 2

        # Rozdelenie pola na dve časti

        L = pole[:stred]
        P = pole[stred:]

        # Zoradenie najskôr prvej časti pola, potom druhej

        MergeSort(L)
        MergeSort(P)

        i = j = k = 0

        # Zlúčenie a zoradenie údajov z pomocných polí do jedného pola

        while i < len(L) and j < len(P):
            if L[i] < P[j]:
                pole[k] = L[i]
                i += 1
            else:
                pole[k] = P[j]
                j += 1
            k += 1

        # Kontrola či všetky prvky boli zlúčené dokopy,
        # ak nie, tak sa do zlúčeného pola jednoducho skopírujú

        while i < len(L):
            pole[k] = L[i]
            i += 1
            k += 1

        while j < len(P):
            pole[k] = P[j]
            j += 1
            k += 1


# Hlavný program

if __name__ == '__main__':

    pole = [12, 11, 13, 5, 6, 7]

    print("Zadané pole:", end="\n")
    print(pole, end="\n")

    MergeSort(pole)

    print("Zoradené pole:", end="\n")
    print(pole, end="\n")

def MergeSort_iteracia(pole):

    # Dĺžka subpolí, ktoré majú byť zlúčené, hodnoty premennej sa pohybujú v intervale <1;n-1>

    aktual_dlzka = 1

    # Vonkajší cyklus, ktorý určuje subpolia aktuálnej dĺžky

    while aktual_dlzka < len(pole) - 1:

        lavy = 0

        # Vnútorný cyklus, ktorý slúži na zlúčenie a zoradenie subpoli do jedného subpola

        while lavy < len(pole) - 1:

            # Index stredného prvku sa určí, keď k indexu ľavého prvku subpola pripočítame aktuálnu
            # dĺžku subpolí a odčítame 1

            stred = min((lavy + aktual_dlzka - 1), len(pole) - 1)

            # Ak platí podmienka 2 * aktuálna dĺžka < dĺžka pola - 1, tak pravý index = aktuálnej dĺžke subpolí,
            # inak pravý index = dĺžke pola - 1

            pravy = ((2 * aktual_dlzka + lavy - 1, len(pole) - 1)[2 * aktual_dlzka + lavy - 1 > len(pole) - 1])

            # Volanie funkcie merge

            merge(pole, lavy, stred, pravy)

            lavy = lavy + 2 * aktual_dlzka

        # Aktuálna dĺžka sa sa zmení na dvojnásobok jej predošlej hodnoty

        aktual_dlzka = 2 * aktual_dlzka


def merge(pole, lavy, stred, pravy):

    n1 = stred - lavy + 1
    n2 = pravy - stred

    # Inicializácia pomocných polí

    L = [0] * n1
    P = [0] * n2

    # Načítanie dát do pomocných polí

    for i in range(0, n1):
        L[i] = pole[lavy + i]
    for i in range(0, n2):
        P[i] = pole[stred + i + 1]

    i, j, k = 0, 0, lavy

    # Zlúčenie a zoradenie údajov z pomocných polí do jedného pola

    while i < n1 and j < n2:
        if L[i] > P[j]:
            pole[k] = P[j]
            j += 1
        else:
            pole[k] = L[i]
            i += 1
        k += 1

    # Kontrola či všetky prvky boli zlúčené dokopy,
    # ak nie, tak sa do zlúčeného pola jednoducho skopírujú

    while i < n1:
        pole[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        pole[k] = P[j]
        j += 1
        k += 1


# Hlavný program

if __name__ == '__main__':

    pole = [12, 11, 13, 5, 6, 7]

    print("Zadané pole:", end="\n")
    print(pole, end="\n")

    MergeSort_iteracia(pole)

    print("Zoradené pole:", end="\n")
    print(pole, end="\n")

Odkazy

1. https://www.geeksforgeeks.org/merge-sort/
2. https://www.geeksforgeeks.org/iterative-merge-sort/
3. https://medium.com/@paulsoham/merge-sort-63d75df76388
4. https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort
5. https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.htm
6. https://www.youtube.com/watch?v=6pV2IF0fgKY
7. https://www.youtube.com/watch?v=mB5HXBb_HY8
8. https://www.youtube.com/watch?v=ak-pz7tS5DE