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 de complejidad O(n log n).
Descripción
Fue desarrollado en 1945 por John Von Neumann.[1]
Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:
- Si la longitud de la lista es 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.
- Mezclar las dos sublistas en una sola lista ordenada.
El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:
- Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
- 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.
A continuación se describe el algoritmo en pseudocódigo (se advierte de que no se incluyen casos especiales para vectores vacíos, etc.; una implementación en un lenguaje de programación real debería tener en cuenta estos detalles):
function mergesort(m) var list left, right, result if length(m) ≤ 1 return m else var middle = length(m) / 2 for each x in m up to middle - 1 add x to left for each x in m at and after middle add x to right left = mergesort(left) right = mergesort(right) if last(left) ≤ first(right) append right to left return left result = merge(left, right) return result
function merge(left, right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) if length(left) > 0 append rest(left) to result if length(right) > 0 append rest(right) to result return result
Ordenamiento MergeSort Fue desarrollado en 1945 por John Von Neumman. El método QuickSort divide la estructura en dos y ordena cada mitad recursivamente. El caso del mergesort es el opuesto, en este método se unen dos estructuras ordenadas para formar una sola ordenada correctamente. Este tipo de ordenamiento es útil cuando se tiene una estructura ordenada y los nuevos datos a añadir se almacenan en una estructura temporal para después agregarlos a la estructura original de manera que vuelva a quedar ordenada. • Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera: • Si la longitud de la lista es 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. • 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ñ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.
Comparación con otros algoritmos de ordenamiento
Aunque heapsort tiene los mismos límites de tiempo que merge sort, requiere sólo Θ(1) espacio auxiliar en lugar del Θ(n) de merge sort, y es a menudo más rápido en implementaciones prácticas. Quicksort, sin embargo, es considerado por mucho como el más rápido algoritmo de ordenamiento de propósito general. 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: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera Θ(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el acceso aleatorio hace que otros algoritmos (como quicksort) den un bajo rendimiento, y para otros (como heapsort) sea algo imposible.
Para Perl 5.8, merge sort es el algoritmo de ordenamiento por defecto (lo era quicksort en versiones anteriores de Perl). En Java los métodos de ordenación de Arrays usan merge sort o una modificación de quicksort dependiendo de los tipos de datos y por cuestiones de eficiencia cambian a ordenamiento por inserción cuando se están ordenando menos de siete elementos en el array.
Referencias
- Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0.
Enlaces externos
- Distintas implementaciones del algoritmo en Wikibooks (inglés)
- Distintas implementaciones del algoritmo en RosettaCode.org (inglés)