OrnacionMergesort

“Benemérita Universidad Autónoma de Puebla”
Regional Acatzingo
Análisis y Diseño de Algoritmos

Método de Ordenación Mergesort












Adrián Gómez Fernández
Alan ÁlvarezÁvila
Estudiantes de Ing. En ciencias de la Computación
Mergesort
Definición: Consiste en dividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no seansuficientemente pequeños o triviales.




Ordenamiento por mezcla
Se basa en la técnica divide y vencerás (DYV).
Divide: Divide la secuencia de n elementos en dos subsecuencias de n/2 elementos.Vence: Ordena ambas subsecuencias de manera recursiva.
Combina: Mezcla las dos subsecuencias ordenadas para obtener la solución del problema.
Combina: Mezcla las dos subsecuencias ordenadas paraobtener la solución del problema.











Pseudocódigo
Si A[n..] (n==1)
{
«Esta Ordenado»
}
Si no
Realiza {A[n]/2;
}
Mientras(n=!1)
Mezcla

Funcionamiento
1. Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad deltamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.

Complejidad
El ordenamiento por mezcla tiene unacomplejidad de “O(n logn)”





Ventajas
Método estable de ordenamiento mientras la operación de mezcla (Merge) sea bien implementada.
Este algoritmo es efectivo para conjuntos de datos que se puedanacceder secuencialmente como arreglos, vectores y listas ligadas

Desventajas
Su principal desventaja radica en que está definido recursivamente y su implementación no recursiva emplea una pila,por lo que requiere un espacio adicional de memoria para almacenarla.

Mejor Caso:
Si la longitud de la lista es 0 ó 1, entonces ya está ordenada.

Caso Medio:
Dividir la lista desordenada en...