Ordenamiento por Mergesort

 

Este método de ordenamiento toma la lista de llaves y la divide en dos partes, las cuales se ordenan en forma independiente. Finalmente, las dos listas ordenadas resultantes, se mezclan para formar la lista ordenada final.

Visualmente se puede apreciar de la siguiente manera:

Por ejemplo, realicemos el seguimiento para una lista con los siguientes datos:

7 – 5 – 3 – 9 – 8 – 2 – 6 – 1

La lista de llaves se divide en 2 partes iguales,

Lista1: 7 – 5 – 3 – 9
Lista2: 8 – 2 – 6 – 1

Aplicamos el método de ordenamiento nuevamente para cada una de las listas:

 Una implementación de este método de ordenamiento puede ser:

Lista b;
void MergeSort(Lista a, int l, int r)
{
    int i,j,k,m;
    if (r > l)
    {
        m = (r+l) /2;
        MergeSort(a, l, m);
        MergeSort(a, m+1, r);
        for (i= m+1; i>l;i–)
            b[i-1] = a[i-1];
        for (j= m; j < r; j++)
            b[r+m-j] = a[j+1];
        for (k=l ; k<=r; k++)
            a[k] = (b[i] < b[j]) ? b[i++] : b[j–];
    };
};

 
 

El orden de este método de ordenamiento es de , el cual se desprende de su ecuación de recurrencia: