Intercalación (MERGE) es el proceso de combinar dos o mas archivos (arreglos) ordenados en un tercer archivo ordenado.
Este algoritmo de comparación, es estable ya que se mantiene el orden relativo de registros con claves iguales. Es un tipo de algoritmo “DIVIDE Y VENCERAS”
Fue inventado por John Von Newmann en 1945. <image src=“
“ border=0 />
Proceso
Esta tecnica funciona de la siguiente manera:
* Dividir el archivo en n subarchivos de tamaño 1 e intercalar pares adyacentes (inconexos) de archivos.
Entonces tenemos mas o menos n/2 archivos de tamaño 2.
* Repetir el proceso hasta que solo reste un archivo de tamaño n.
Estabilidad del algoritmo
Cuando los elementos iguales son indistinguibles, como con los enteros, o mas generalmente, cualquier dato en el que el elemento es la llave, la estabilidad no es un problema. Sin embargo, asumamos que los siguientes pares de números se van a ordenar por su primera componente: (4, 1) (3, 7) (3, 1) (5, 6)
En este caso, el resultado puede ser dos ordenaciones posibles, uno que mantiene el orden relativo de los registros con llaves iguales y otro que no:
(3, 7) (3, 1) (4, 1) (5, 6) (Se mantiene) (3, 1) (3, 7) (4, 1) (5, 6) (Se cambia)
Los ordenamientos inestables pueden cambiar el orden relativo, pero en el ordenamiento estable nunca sucede esto.
Para mayor información y ejemplos de implementaciones en diferentes lenguajes de programación visita mi sitio: http://intercalaciondirecta.googlepages.com/
Sitio WEB Recomendado