jueves, 24 de mayo de 2012
Ventajas y Desventajas
- Método de ordenamiento estable mientras la función de mezcla sea implementada correctamente.
- Muy estable cuando la cantidad de registros a acomodar es de índice bajo, en caso contrario gasta el doble del espacio que ocupan inicialmente los datos.
- Efectivo para conjunto de datos a los que se puede acceder secuencialmente (arreglos, vectores, etc.)
- Principal desventaja: está definido recursivamente. Si se deseara implementarla no recursivamente se tendría que emplear una pila y se requeriría un espacio adicional de memoria para almacenarla.
Tiempo de ejecución
No hay más que
log2n pasadas en este algoritmo, y cada
una implica n o menos comparaciones. Por lo tanto, requiere no menos de n log2 n comparaciones.
žEn el peor de
los casos, Mergesort NUNCA requiere mas de n log2 n.
Divide y Vencerás
Consiste en dividir en dos partes el vector a ordenar, ordenar por separado cada una de esas partes y finalmente
mezclar ambas partes, manteniendo el orden en un solo vector ordenado.
Este algoritmo es una estrategia básica de “Divide y vencerás”.
- DIVIDIR: Divide la secuencia de “n” elementos a ordenar en dos subsecuencias de “n/2” elementos cada una.
- VENCER: Ordena las dos subsecuencias en una sola de manera recursiva.
Antecedentes
El algoritmo de Merge Sort fue desarrollado por el matemático húngaro John Von Neumann en 1945.
ž
Éste algoritmo sirve para ordenar secuencias de datos. También se le conoce como Método de Intercalación o Método de Combinación.
Suscribirse a:
Entradas (Atom)