====== MergeSort ======

===== Princip =====
  - rozdělíme seznam(pole) na dva(dvě) přibližně stejné velikosti  
  - oba seznamy(pole) seřadíme 
  - seřazené seznamy(pole) spojíme (postupně porovnáváme oba seznamy(pole) a do výsledného zařazujeme menší prvky, nakonec přidáme zbytek prvního nebo druhého).
===== Složitost =====
Asymptotická složitost MergeSort je O(n log n).

===== Řešení =====
==== Varianta 1 ====
MergeSort pomocí rekurze.
<code java>
static int [] MergeSort (int[] npole)
    {
        if (npole.length==1) return npole;
        else
        {
            int stred;              //stred pole
            int[] levacast;         //leva cast
            int[] pravacast;         //prava cast
            int i;                  //index v poli

            stred=npole.length/2;
            levacast = new int[stred];
            pravacast = new int[npole.length-stred];
            for (i=0;i<stred;i++)               //naplneni leve pulky
            {
                levacast[i]=npole[i];
            }
            for (i=0;i<npole.length-stred;i++)  //naplneni prave pulky
            {
                pravacast[i]=npole[i+stred];
            }
            levacast=MergeSort(levacast);       //setrid levou
            pravacast=MergeSort(pravacast);     //setrid pravou
            npole=Merge(levacast,pravacast);    //spoj setridene
            return npole;
        }
    }

    static int[] Merge(int[] leva, int[] prava)
    {
        int[] spojenepole;
        spojenepole = new int[leva.length+prava.length];
        int i = 0;
        int j = 0;
        while (i<leva.length&&j<prava.length)
        {
            if (leva[i]<prava[j])           //do vysledku patri pouze mensi prvek
            {
                spojenepole[i+j]=leva[i];   //pridani mensiho
                i++;                        //prislusny index odkud se bralo
            }
            else
            {
                spojenepole[i+j]=prava[j];  //pridani mensiho
                j++;                        //prislusny index odkud se bralo
            }
        }
        while (i<leva.length)               //musime doplnit zbytek je odtud?
            {
            spojenepole[i+j]=leva[i];
            i++;
            }
        while (j<prava.length)              //musime doplnit zbytek je odtud?
            {
            spojenepole[i+j]=prava[i];
            j++;
            }
        return spojenepole;
    }
    
</code>

==== Varianta 2 ====
MergeSort nerekurzivně - viz přednáška.