Merge Sort

Mergesort
Antecedentes
Algoritmo del tipo “Divide y vencerás”, el cual consiste en tomar un problema original de forma ordenada y subdividirlos en otros problemas más simples de más o menos lamitad del tamaño, creado en 1946 por John Mauchly, éste algoritmo se dice que tiene sus orígenes de la antigua Babilonia en el año 200 A.C, en el cual planteaban una lista ordenada de números parafacilitar la búsqueda de algún elemento dentro de esa lista.

Mejor, peor y caso promedio
Mejor caso
En el caso de Mergesort el mejor caso es cuando se realiza una sola comparación, es decir cuando elelemento buscado es el primer punto medio obtenido de la suma del índice inicial y el último.
Peor caso
El peor caso se da cuando requiere un tiempo de log2 N, es decir mientras más divisiones ycomparaciones con el punto medio haya peor, por lo cual si se da el caso de realizar la mayor cantidad de divisiones en un arreglo sería el peor caso para éste algoritmo.
Caso promedio
En éste caso, noes muy claro cuando sería un caso promedio, por lo cual se dice que éste algoritmo no tiene un caso promedio.






Complejidad tiempo y espacio
A continuación se entregan resultados de pruebashechas con el algoritmo de búsqueda Binaria en Arreglos con 50, 100, 500, 1000, 5000, 10000, 50000, 100000 y 500000

Datos ordenados
Tiempo promedio Cantidad Iteraciones
Con 50 datos00:00:00.0000021 5
Con 100 datos 00:00:00.0000029 11
Con 500 datos 00:00:00.0000051 17
Con 1000 datos 00:00:00.0000055 19
Con 5000 datos 00:00:00.0000068 23
Con 10000 datos 00:00:00.0000108 25
Con 50000datos 00:00:00.0000145 29
Con 100000 datos 00:00:00.0000102 33
Con 500000 datos 00:00:00.0000153 37










Resultado experimental prototipo
Trazabilidad de ejemplo
Supongamos elsiguiente arreglo ordenado de 5 datos, con los índices “i” y “j”, nos ponemos en el caso de buscar el número 7.
5 7 15 21 30


21 30
15
Primero se saca el punto medio del arreglo sumando la posición...