Page 65 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 65
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
A(6) y A(7) son fusionados y entonces A(8) se fusiona con A(6:7), lo que origina:
(179, 285, 310, 351, 652, |254, 423, 861|450, 520)
El siguiente paso es A(9) y A(10) son fusionados siguiendo A(6:8) y A(9:10):
(179, 285, 310, 351, 652|254, 423, 450, 520, 861).
En este momento se tienen dos subarreglos ordenados y la fusión final produce la ordenación com-
pleta:
(179, 254, 285, 310, 351, 423, 450, 520, 652, 861).
A continuación, la figura 2.1 enseña la secuencia de recursividades producidas por merge sort con
los diez elementos, así como la forma en que se van a dividir los subarreglos. Véase que la división
continúa hasta contener un simple elemento.
Figura 2.1. Árbol recursivo para el algoritmo merge sort
Ahora, en la figura 2.2 se aprecia la parte de división de un arreglo, la parte de ordenación de cada
uno de los subarreglos, así como sus respectivas fusiones hasta conseguir el arreglo ordenado.
59
