MergeSort

1. rozdělíme seznam(pole) na dva(dvě) přibližně stejné velikosti
2. oba seznamy(pole) seřadíme
3. 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).

Asymptotická složitost MergeSort je O(n log n).

MergeSort pomocí rekurze.

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;
    }
 

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