170 Ordenamiento, Búsqueda e Intercalación
7.3 Método de intercalación
El método de Intercalación, también conocido como Merge en inglés, consiste en intercalar
los valores de dos arreglos ordenados de igual manera, tal que se forme un tercer arreglo igual-
mente ordenado con los elementos de los dos arreglos originales.Considerando dos arreglos
ordenados en forma ascendente:
A = (1, 7, 18, 23)
B = (2, 5, 6, 9, 12, 16, 17)
se trata de componer un nuevo arreglo ordenado:
C = (1, 2, 5, 6, 7, 9, 12, 16, 17, 18, 23)
donde los elementos de C se han obtenido intercalando las de A y B.
Un criterio muy poco eficiente para resolver el problema sería construir un arreglo D colo-
cando los elementos de B a continuación de los de A y luego reordenarlo partiendo de D = (1,
7, 18, 23,2, 5, 6, 9, 12, 16, 17)En esta forma se pierde la ventaja de que A y B ya hayan sido
ordenados, y aumenta el tiempo de ejecución.
El método de Intercalación compara los primeros elementos de A y de B y coloca en C el
menor de ellos (por estar ordenados en forma ascendente), descartando dicho elemento. Luego
continúa con los restantes, hasta que alguno de los dos arreglos se haya traspasado completa-
mente a C, quedando las últimas componentes del otro arreglo por pasar. En el caso del ejemplo,
los valores del arreglo B serán pasados a C, quedando el 18 y el 23 del arreglo A por pasar.
Algoritmo intercalar
arreglo [1,10000] real: A, B
arreglo [1,20000] real: C
! C debe contener las comp. de A y las de B
entero: n, m, i, inda, indb
inicio
Leer (n) ! cantidad de componentes de A
Repetir Para i ← 1, n
Leer (A[i])
finpara
Leer (m) ! cantidad de componentes de B
Repetir Para i ← 1, m
Leer (B[i])
finpara
inda ← 1
indb ← 1 ! próxima componente en cada arreglo
! intercalación
Repetir Para i ← 1, n+m ! llenar cada componente de C
Si (inda <= n y indb <= m) entonces
! hay componentes disponibles
Si (A[inda] < B[indb]) entonces
C[i] ← A[inda]