14.09.2022

El invariante de ciclo para la función Mezcla()

Para demostrar que el algoritmo es correcto,
tenemos el invariante del ciclo:

Al inicio de la cada iteración para el ciclo for de las líneas 12-18,
el subarreglo A[p..k-1] contiene los k-p elementos más pequeños de I[1..n1+1] 
y D[1..n2+1], ordenados. Aún más, I[i] y D[j] son los elementos más pequeños
de sus arreglos que no se han copiado al arreglo A.

Initializatión: Antes de la inicialización del ciclo for, se tiene
    k = p, de forma que el subarreglo A[p..k-1] está vacio. Este subarreglo
    vacio contiene los k - p = 0 elementos más pequeños de I y D ya que i=1, j=1,
    pero I[i] y D[j] son los elementos más pequeños de sus arreglos respectivos
    que no han sido copiados hacia A. 

Mantenimiento: Para ver que en cada iteración se mantiene el invariante del ciclo,
    supongamos que I[i] <= D[j]. Entonces I[i] es el elemento más pequeño que no ha 
    sido copiado a A. Debido a que A[p..k-1] contiene los k-p elementos más pequeños,
    después de la línea 14 copia I[i] a A[k], el subarreglo A[p..k] contendrá k-p+1
    elementos más pequeños. Incrementando k e i se reestable el invariante del ciclo
    para la siguiente iteración. Si tenemos que I[i] > D[j], las líneas 16-18 realizan
    la acción apropiada para mantener el invariante.

Terminación: Al terminar, k=r+1. Por el invariante, el arreglo A[p...k-1], el cuál
    es A[p..r], contiene los k-p=r-p+1 elementos más pequeños de I[1..n1+1] y D[1..n2+1],
    ordenados. Los arreglos I y D juntos contienen n1 + n2 + 2 = r - p + 3 elementos.
    Los elementos más grandes, los sentinelas siguen en esos arreglos I y D y estos
    elementos son los sentinelas.