Bachillerato

Ordenamiento por mezcla

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:
1. Si la longitud de la lista es 0 ó 1,entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
3. Ordenar cada sublistarecursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.
El ordenamiento por mezcla incorpora dosideas principales para mejorar su tiempo de ejecución:
1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitanmenos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo seránecesario entrelazar cada lista una vez que están ordenadas.
A continuación se describe el algoritmo en pseudocódigo (se advierte de que no se incluyencasos especiales para vectores vacíos, etc.; una implementación en un lenguaje de programación real debería tener en cuenta estos detalles):
functionmergesort(array A[x..y])
begin
if ((y-x) > 0):
array A1 := mergesort(A[x..(int( x+y / 2))])
array A2 := mergesort(A[int(1+(x+y / 2))..y])return merge(A1, A2)
else:
return A
end

function merge(array A1[0..n1], array A2[0..n2])
begin
integer p1 := 0
integer p2 := 0
arrayR[0..(n1 + n2 + 2)]//suponiendo que n1 y n2 son las posiciones
//del array y no el length de este mismo, de otro modo seria (n1 + n2)
while (p1