Page 64 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Considere el arreglo de diez elementos A (310, 285, 179, 652, 351, 423, 861, 254, 450, 520). Mer-
ge sort inicia por dividir A en dos subarreglos de tamaño cinco. Los elementos A(1:5) son a su vez
divididos en arreglos de tamaño tres y dos. Entonces, los elementos A(1:3) son divididos en dos
subarreglos de tamaño dos y uno. Los dos valores en A(1:2) son divididos en un subarreglo de un
solo elemento y la fusión inicia. Hasta este momento ningún movimiento ha sido realizado. Pictórica-
mente, el arreglo puede ser visto de la siguiente forma:
(310|285|179|652, 351|423, 861, 254, 450, 520).

Las barras verticales indican el acotamiento de los subarreglos. A(1) y A(2) son fusionados, lo que
produce:
(285, 310| 179|652, 351| 423, 861, 254, 450, 520).

Entonces, A(3) es fusionado con A(1:2), lo que genera:

(179, 285, 310|652, 351|423, 861,254, 450, 520)

Los elementos A(4) y A(5) son fusionados:

(179, 285, 310|351, 652| 423, 861, 254, 450, 520)

Siguiendo la fusión de A(1:3) y A(4:5), se tiene:

(179, 285, 310, 351, 652| 423, 861, 254, 450, 520)

En este punto, el algoritmo ha retornado a la primera invocación de merge sort y se realizará la se-
gunda llamada recursiva. Las llamadas recursivas a la derecha producen los siguientes subarreglos:

(179, 285, 310, 351, 652|423|861|254|450, 520).

58