mergesort

Introducción


Este algoritmo fue desarrollado por el matemático húngaro John Von Neumann quien fue un matemático húngaro-estadounidense, de ascendencia judía, que realizó contribuciones importantes en física cuántica, análisis funcional, teoría de conjuntos, informática, economía, análisis numérico, hidrodinámica (de explosiones), estadística y muchos otros campos. Recibió su doctorado enmatemáticas de la Universidad de Budapest a los 23 años.

El método de ordenación por Mezcla se adapta muy bien a distintas circunstancias, por lo que es comúnmente utilizado no sólo para la ordenación de vectores. Por ejemplo, el método puede ser también implementado de forma que el acceso a los datos se realice de forma secuencial, por lo que hay diversas estructuras (como las listas enlazadas)para las que es especialmente apropiado. También se utiliza para realizar ordenación externa, en donde el vector a ordenar reside en dispositivos externos de acceso secuencial (i.e. ficheros).
















Características.

• Es un algoritmo recursivo con un número de comparaciones mínimo. El tiempo de ejecución promedio es O(N log(N)).

• Su desventaja es que trabaja sobreun array auxiliar lo cual tiene dos consecuencias:
uso de memoria extra y trabajo extra consumido en las copias entre arreglos (aunquees un trabajo de tiempo lineal).

• Es una aplicación clásica de la estrategia para resolución de algoritmos "divide yencerás". Esta estrategia plantea el hecho de que un problema puede ser dividido en varios subproblemas y una vez resueltos estos se puedeproceder a unir las soluciones para formar la solución del problema general. La solución de los subproblemas más pequeños se realiza de la misma manera: es decir, se van resolviendo problemas cada vez más pequeños (hasta encontrarnos con un caso base: problema no divisible con solución trivial)

















Funcionamiento

El proceso de este algoritmo es fusionar sucesivamentemitades ya ordenadas de datos:

El grupo de datos a ordenar es dividido en sus dos mitades pues es más sencillo ordenar una parte de los datos que el conjunto completo de ellos, cuando quede un solo dato en un subgrupo se termina el proceso de división pues ese subgrupo ya está ordenado. A continuación, se mezclan ambas mitades ordenando los datos a medida que se combinan, para ello se empleaun algoritmo sencillo que requiere un espacio auxiliar del tamaño del grupo original para añadir el dato correspondiente de cada subgrupo así:






Se comparan entonces los elementos de la mitad 1 en la posición pos1 y de la mitad 2 en la posición pos2, el menor se copia en ‘mezcla’ en la posición posMezcla, se incrementan las posiciones del origen que se ha copiado (pos1 o pos2) y la delespacio de destino (posMezcla) y se compara el nuevo par de elementos; finalmente alguna de las dos mitades habrá sido copiada completamente, entonces se debe copiar en el espacio de mezcla los elementos que hayan quedado sin copiar de la otra mitad.

El método de mezcla realiza un número de comparaciones que aumenta linealmente con el número de elementos a
Este es un diagrama de árbol delfuncionamiento del Algoritmo:







EL ALGORITMO MERGESORT EN PSEUDO-CÓDIGO

Método MergeSort(arreglo)
//Primero se procede a dividir el arreglo, pero esto sólo será necesario cuando él tenga mínimo 2 elementos:
if (arreglo tiene más de 1 elemento)
//Se hacen llamadas recursivas para dividir la primera y segunda mitad del arreglo .
MergeSort(primera mitad del arreglo)MergeSort(segunda mitad del arreglo)
//Se combinan las mitades
Merge(mitad 1, mitad 2)
fin (if)
fin MergeSort
método Merge(arreglo1, arreglo2)

//Se define un nuevo arreglo en el cual se almacenará la mezcla de los arreglos.
Define arregloMezcla
//se inicializan 3 enteros que controlen la posición en los arreglos 1, 2 y mezcla.
i1, i2, i3 inicializados en 0
//Se empezará el proceso de mezcla y...