Ordenamiento por mezcla - MergeSort

MergeSort es un algoritmo de ordenamiento basado en la estrategia "divide y vencerás". Su orden asintótico es O(n log n), mucho mas eficiente que otros algoritmos de ordenamiento como burbuja, inserción o selección que son de orden cuadrático.

Básicamente MergeSort actúa de esta manera:

1. Si la longitud del vector es 1 significa que ya esta ordenado y no hace nada.
2. Sino, divide en vector por la mitad en dos subvectores.
3. Ordena cada subvector de forma recursiva.
4. Finalmente mezcla los subvectores ya ordenados uniéndolos en un solo vector ordenado.

Fig. 1 - Ejemplo de Mergesort.

Hay que destacar que la función que mezcla los subvectores (merge) es de tiempo lineal ya que solo tiene que sacar cada vez el mayor elemento de ambos subvectores (que ya están ordenados) y colocarlo consecutivamente en el vector resultante.

Ahora veamos una implementación del MergeSort en C++:

/*
Algoritmo de ordenamiento MergeSort.
Por: Alguien
Fecha: Domingo 09 de mayo del 2010
*/
#include <stdlib.h>
#include <stdio.h>

void mergesort(int *v, int i, int f);
void merge(int *v, int i, int m, int f);

int main() {
 int *v, n;
 printf("Ingrese N: ");
 scanf("%d", &n);
 
 v = new int[n];
 for(int i=0; i<n; i++) {
  printf("Elemento %d: ", i+1);
  scanf("%d", &v[i]);
 }
 
 mergesort(v, 0, n-1);
 
 for(int i=0; i<n; i++)
  printf("%d ", v[i]);
 
 return 0;
}

void mergesort(int *v, int i, int f) {
 if(i!=f) {
  int m = (i+f)/2;
  mergesort(v, i, m);
  mergesort(v, m+1, f);
  merge(v, i, m, f);
 }
}

void merge(int *v, int i, int m, int f) {
 int *aux = new int[m-i+1];
 for(int j=i; j<=m; j++)
  aux[j-i] = v[j];
 
 int c1=0, c2=m+1;
 for(int j=i; j<=f; j++) {
  if(aux[c1] < v[c2]) {
   v[j] = aux[c1++];
   if(c1==m-i+1)
    for(int k=c2; k<=f; k++)
     v[++j] = v[k];
  }
  else {
   v[j] = v[c2++];
   if(c2==f+1)
    for(int k=c1; k<=m-i; k++)
     v[++j] = aux[k];
  }
 } 
}

Saludos.