Merge Sort
Este algoritmo también es llamado de intercalación o combinación, debido que combina (intercala) dos estructuras previamente ordenadas.
Historia
Fue desarrollado en 1946 por John Von Neumann. Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:Si la longitud de la lista es de 0 o 1, entonces ya está ordenada. En otro caso:
-
Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.Mezclas las dos sublistas en una sola lista ordenada. El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:
1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.
Ventajas
Método estable de ordenamiento mientras la operación de mezclas (merge) está bien implementada.Este algoritmo es efectivo para conjuntos de datos que se puedan acceder como arreglos, vectores y listas ligadas.
Desventajas
Está definido recursivamente y su implementación no recursiva emplea una pila, por lo que requiere un espacio adicional de memoria para almacenarla. En el lado bueno, merge sort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento. Merge sort es a menudo la mejor opción para ordenar una lista enlazada.
Conceptualmente, una combinación de tipo funciona de la siguiente manera:
1. Divida la lista sin ordenar en n sub-listas, cada una contiene 1 elemento (una lista de 1 elemento se considera clasificada).
2. Repetidamente fusionar listas secundarias para producir nuevas sublistas ordenadas hasta que sólo 1 sublista restante. Esta será la lista ordenada.
Complejidad
El algoritmo es recursivo esa razón que se quiere determinar el tiempo empleado por cada una de las 3 fases del algoritmo divide y vencerás. Cuando se llama a la función mezclista se deben mezclar las dos listas más pequeñas en una nueva lista con n elementos. La función hace una pasada a cada una de las sublistas. Por consiguiente, el número de operaciones realizadas será como máximo el producto de una constante multiplicada por n. si se consideran las llamadas recursivas se tendrá entonces el número de operaciones: constante *n* (profundidad de llamadas recursivas). El tamaño de la lista a ordenar se divide por dos en cada llamada recursiva, de modo que el número de llamadas es aproximadamente igual al número de veces que n se puede dividir por 2, parándose cuando el resultado es menor o igual a 1.Por consiguiente, la ordenación por mezcla se ejecutará, aproximadamente, el número de operaciones: alguna constante multiplicada por n y después por (logn), Resumiendo hay dos llamadas recursivas, y una iteración que tarda tiempo n por lo tanto la recurrencia es:
Bibliografía:
Busqueda Secuencial
 |  |  |  |
|---|---|---|---|
 |
Inorden
 |  |
|---|---|
 |  |
Bubble Sort
Método Binario
Preorden
Preorden