Método de ordenación MergeSort

El método MergeSort es un algoritmo de ordenación recursivo con un número de comparaciones entre elementos del array mínimo.

Su funcionamiento es similar al Quicksort, y está basado en la técnica divide y vencerás.

De forma resumida el funcionamiento del método MergeSort es el siguiente:

- Si la longitud del array es menor o igual a 1 entonces ya está ordenado.

- El array a ordenar se divide en dos mitades de tamaño similar.

- Cada mitad se ordena de forma recursiva aplicando el método MergeSort.

- A continuación las dos mitades ya ordenadas se mezclan formando una secuencia ordenada.

La ordenación mergesort se puede implementar en Java de la siguiente forma:

public static void mergesort(int A[],int izq, int der){
    if (izq < der){
            int m=(izq+der)/2;
            mergesort(A,izq, m);
            mergesort(A,m+1, der);                                                                                
            merge(A,izq, m, der);                                                                                 
    }
}

El método ordena un array A de enteros desde la posición izq hasta la posición der. En la primera llamada al método recibirá los valores izq = 0, der = ELEMENTOS-1.

Primero se calcula el elemento central m. A continuación la primera parte del array, desde izq hasta m y la segunda parte del array, desde m+1 hasta der, se mezclan mediante llamadas recursivas al método mergesort.

La recursión termina cuando izq == der, es decir, cuando un subarray contiene solamente un elemento.

La operación principal de mezcla la realiza el método merge. Este método se puede implementar de varias formas, la más usual es la siguiente:

public static void merge(int A[],int izq, int m, int der){
   int i, j, k;
   int [] B = new int[A.length]; //array auxiliar
   for (i=izq; i<=der; i++)      //copia ambas mitades en el array auxiliar                                       
        B[i]=A[i];

   i=izq; j=m+1; k=izq;
     
   while (i<=m && j<=der) //copia el siguiente elemento más grande                                      
          if (B[i]<=B[j])
              A[k++]=B[i++];
          else
              A[k++]=B[j++];
        
   while (i<=m)         //copia los elementos que quedan de la
         A[k++]=B[i++]; //primera mitad (si los hay)
}

De forma gráfica podemos representar el funcionamiento del algoritmo de la siguiente forma:

El tiempo de ejecución promedio del método MergeSort es O(n log n).