MergeSort (Ordenamiento por Mezcla)
Est basado en la tcnica de divide y vencers . Primero toma el arreglo original de datos, lo divide
en dos partes del mismo tamao cada una, y lo sigue dividiendo hasta que solo quede un elemento.
Cada una de las divisiones se ordena de manera separada y luego se unen para formar el arreglo ya
ordenado. Este algoritmo divide inicialmente la lista hasta su mnimo valor y luego ordena el arreglo.
Ejemplo grfico
Como estamos usando divide y vencers para ordenar, tenemos que decidir cmo se van a ver
nuestros subproblemas. El problema completo es ordenar todo un arreglo. Digamos que un
subproblema es ordenar un subarreglo. En particular, vamos a pensar que un subproblema es
ordenar el subarreglo que empieza en el ndice p y va hasta el ndice r. Ser conveniente tener una
notacin para un subarreglo, as que digamos que array[p..r] denota este subarreglo de array.
En trminos de nuestra notacin, para un arreglo de n elementos, podemos decir que el problema
original es ordenar array[0..n-1].
Aqu est cmo el ordenamiento por mezcla utiliza divide y vencers:
1. Divide al encontrar el nmero q de la posicin a medio camino entre p y r. Haz este paso de
la misma manera en que encontramos el punto medio en la bsqueda binaria: suma p y r,
divide entre 2 y redondea hacia abajo.
2. Vence al ordenar de manera recursiva los subarreglos en cada uno de los dos subproblemas
creados por el paso de dividir. Es decir, ordena de manera recursiva el subarreglo
array[p..q] y ordena de manera recursiva el subarreglo array[q+1..r].
3. Combina al mezclar los dos subarreglos ordenados de regreso en un solo subarreglo
ordenado array[p..r].
Necesitamos un caso base. El caso base es el subarreglo que contiene menos de dos elementos, es
decir, cuando p r, ya que un subarreglo sin elementos o con solo un elemento ya est ordenado.
As que vamos a dividir-vencer-combinar solo cuando p<r.
Veamos un ejemplo. Vamos a empezar con array que contiene a [14, 7, 3, 12, 9, 11, 6, 2], de modo
que el primer subarreglo es en realidad el arreglo completo, array[0..7] (p = 0 y r = 7). Este
subarreglo tiene por lo menos dos elementos, as que no es un caso base.
En el paso de dividir, calculamos q = 3.
El paso de vencer nos hace ordenar los dos subarreglos array[0..3], que contiene a [14,
7, 3, 12], y array[4..7], que contiene a [9, 11, 6, 2]. Cuando regresamos del paso de
vencer, cada uno de los dos subarreglos est ordenado: array[0..3] contiene a [3, 7, 12,
14] y array[4..7] contiene a [2, 6, 9, 11], de modo que el arreglo completo es [3, 7, 12,
14, 2, 6, 9, 11].
Por ltimo, el paso de combinar mezcla los dos subarreglos en la primera y la segunda
mitad, para producir el arreglo final ordenado [2, 3, 6, 7, 9, 11, 12, 14].
1
Cmo se orden el subarreglo array[0..3]? Del mismo modo. Tiene ms de dos elementos, as
que no es un caso base. Con p=0 y r=3, calcula q=1, ordena recursivamente array[0..1] ([14, 7])
y array[2..3] ([3, 12]), cuyo resultado es array[0..3] que contiene a [7, 14, 3, 12], y mezcla
la primera mitad con la segunda mitad, para producir [3, 7, 12, 14].
Cmo se orden el subarreglo array[0..1]? Con p=0 y r=1, calcula q=0, ordena recursivamente
array[0..0] ([14]) y array[1..1] ([7]), cuyo resultado es array[0..1] que sigue conteniendo
a [14, 7], y mezcla la primera mitad con la segunda mitad, para producir [7, 14].
Los subarreglos array[0..0] y array[1..1] son casos base, ya que cada uno contiene menos
de dos elementos.
Aqu est cmo se desarrolla todo el algoritmo del ordenamiento por mezcla:
La mayora de los pasos en el ordenamiento por mezcla son sencillos. Puedes revisar el caso base
fcilmente. Encontrar el punto medio q en el paso de dividir tambin es muy fcil. Tienes que hacer
2
dos llamadas recursivas en el paso de vencer. Es en el paso de combinar, en donde tienes que
mezclar dos subarreglos ordenados, en donde ocurre el trabajo verdadero.