Método de ordenación Merge Sort

El algoritmo de ordenamiento por mezcla (merge sort) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de Complejidad O(nlog n). 

Una técnica muy poderosa para el diseño de algoritmos es "Dividir para conquistar". Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases:

Dividir: Se divide el problema en partes más pequeñas.

Conquistar: Se resuelven recursivamente los problemas más chicos.

Combinar: Los problemas mas chicos de combinan para resolver el grande.

Los algoritmos que utilizan este principio son en la mayoría de los casos netamente recursivos como es el caso de mergesort.

El algoritmo de Mergesort es un ejemplo clásico de algoritmo que utiliza el principio de dividir para conquistar. Si el vector tiene más de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace una intercalación de las dos mitades ordenadas.

Ejemplo en c++:

// En el código usamos la clase vector (#include <vector.h>) para crear los vectores,
// obviamente funciona igual de bien si se utilizan los arrays tipo C: TIPO V[]
template <class T, class U>
void fusiona(vector<T>& v, U ini, U med, U fin) {
    vector<T> aux(fin - ini + 1);
    int i = ini; // Índice de la parte izquierda
    int j = med + 1; // Índice de la parte derecha
    int k = 0; // Índice del vector aux
 
 
    /* Mientras ninguno de los indices llegue a su fin vamos realizando
       comparaciones. El elemento más pequeño se copia al vector aux */
    while (i <= med && j <= fin) {
        if (v[i] < v[j]) {
            aux[k] = v[i];
            i++;
        }
        else {
            aux[k] = v[j];
            j++;
        }
        k++;
    }
 
    /* Uno de los dos sub-vectores ya ha sido copiado del todo, simplemente
       debemos copiar todo el sub-vector que nos falte */
    while (i <= med) {
        aux[k] = v[i];
        i++;
        k++;
    }
 
    while (j <= fin) {
        aux[k] = v[j];
        j++;
        k++;
    }
 
    /* Copiamos los elementos ordenados de aux al vector original v */
    for (int n = 0; n < aux.size(); ++n) v[ini + n] = aux[n];
}
 
template <class T, class U>
void merge_sort(vector<T>& v, U ini, U fin) {
    /* Si ini = fin el sub-vector es de un solo elemento y, por lo tanto
       ya está ordenado por definición */
    if (ini < fin) {
/*Considerar que el valor de med siempre es redondeado hacia abajo.*/
        int med = (ini + fin)/2;
        merge_sort(v, ini, med);
        merge_sort(v, med + 1, fin);
        fusiona(v, ini, med, fin);
    }
}