La Leyenda De La Llorona

Merge
Ordenamiento por mezcla
El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es decomplejidad O(n log n).
Fue desarrollado en 1945 por John Von Neumann.[cita requerida]
Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:
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 del tamaño.
3. Ordenar cada sublista recursivamente aplicando elordenamiento por mezcla.
4. Mezclar 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ñanecesitará 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 listasdesordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.
EJEMPLO

Optimizando merge sort
En los ordenadores modernos, el principio de localidad puede serprimordial en la optimización de software, porque se usan jerarquías de memoria multi-nivel. Se han propuesto versiones de cache-consciente del algoritmo de ordenación por mezcla, cuyas operaciones han sidoespecíficamente escogidas para minimizar el movimiento de entrada y salida de páginas de la memoria caché de la máquina. Por ejemplo, el algorimo "tiled merge sort" deja de particionar subarrayscuando se han alcanzado subarrays de tamaño S, donde S es el número de elementos que caben en una única página en memoria. Cada uno de esos subarrays se ordenan con un algorimo de ordenación in-situ, paraevitar intercambios en memoria, y entonces se termina con el algoritmo de ordenamiento por mezcla en su versión recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento en máquinas que...