Metodos Ordenamiento

MERGESORT
Este algoritmo fue desarrollado por el matemático húngaro John Von Neumann en 1945.
[Thomas Cormen, 2001].

Consiste en dividir en dos partes iguales el vector a ordenar, ordenar porseparado cada una de las partes, y luego mezclar ambas partes, manteniendo el orden, en un solo vector ordenado.

El algoritmo MergeSort (u Ordenamiento por mezcla) es un algoritmo que sirve paraordenar secuencias de datos.

Utiliza los siguientes tres pasos:
DIVIDIR: divide la secuencia de "n" elementos a ordenar en dos subsecuencias de "n/2" elementos cada una.
VENCER: ordena las dossubsecuencias de manera recursiva mediante el algoritmo MERGESORT.
COMBINAR: combina las dos subsecuencias ordenadas para generar la solución.

ANÁLISIS
Como cualquiera de los algoritmos de ordenamientorecursivo tiene complejidad logarítmica: O(n log2n).
Si el tiempo de ordenamiento de MergeSort para una lista de n elementos es T(n) entonces la repetición T(n) = 2T( n/2 ) + n sigue de ladefinición del algoritmo (Aplicar el algoritmo a las dos listas de la mitad del tamaño de la lista original y aumentar los n pasos tomados para utilizar MergeSort en las dos listas resultantes).
Algoritmo deordenación :

Solución de la ecuación T (n) = 2T (n/2) + O(n)

FUNCIONAMIENTO
El proceso de este algoritmo es fusionar sucesivamente mitades ya ordenadas de datos:
El grupo de datos a ordenar esdividido 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 esesubgrupo ya está ordenado. A continuación, se mezclan ambas mitades ordenando los datos a medida que se combinan, para ello se emplea un algoritmo sencillo que requiere un espacio auxiliar del tamañodel 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...