La operación que hace funcionar el ordenamiento por
mezcla. Los dos tramos ordenados se copian, y en cada vuelta el menor
pendiente de las dos copias se escribe sobre el arreglo. Esa regla tan
simple esconde una pareja de invariantes igual a las de la clase de
ciclos: encuéntrelos y certifique el algoritmo con inicialización y
estabilidad.
1. Antes de ejecutar, prediga
Arreglos (con sus dos tramos ordenados):
¿Cuántas posiciones de lista escribirá la mezcla?
2. Ejecute y mire el arreglo y sus copias
Paso 0 de 0
Fíjese en la segunda escritura del primer arreglo:
tapa el 4 cuando el 4 aún no ha salido — por eso la mezcla lee de las
copias y no del tramo. Y pruebe los otros dos arreglos: en uno se
agota primero la copia izquierda y quedan «sobras»; en el otro hay
empates y el <= decide quién sale primero.
3. La traza, escritura por escritura
Comparación
k
lista
4. Los dos invariantes del primer while
Al comenzar cada vuelta, ¿qué es siempre
cierto del tramo ya escrito, lista[ini..k)? (ese será I₁)
¿Y las cotas de los índices? (ese será I₀)
5. La demostración, para el ciclo nuevo
Encuentre primero los
dos invariantes en la tarjeta 4. El teorema a demostrar es el de la
clase: Teorema 1 — los invariantes I₀ e I₁ se cumplen.
Inicialización
Por las líneas 1–12: izq y der son copias de
los dos tramos, i = 0, j = 0 y k = ini. I₀: 0 ≤ 0 ≤ len(izq),
0 ≤ 0 ≤ len(der) y k = ini + 0 + 0. ✓ I₁: el tramo
lista[ini..ini) es vacío y contiene los 0 menores, en orden: cierto
sin esfuerzo. ✓
Estabilidad
Se asumen los invariantes antes de una vuelta
arbitraria; la condición del while da i < len(izq) y j < len(der),
así que izq[i] y der[j] existen. Hay dos casos, según la comparación.
Si izq[i] <= der[j], se escribe izq[i] en lista[k]. ¿Por qué eso
conserva I₁? izq[i] es el menor pendiente de izq por estar izq
ordenada; y como izq[i] <= der[j] y der está ordenada, también es
≤ que todo pendiente de der. Es el menor de todos los pendientes, y va
justo después de los i + j ya escritos, que por I₁ son los menores: el
tramo sigue en orden y ahora tiene los i + j + 1 menores. El otro caso
es simétrico con der[j]. En ambos, el índice de la copia que aportó
sube en 1 —dentro de sus cotas, porque esa copia aún tenía
elementos— y k sube en 1, así que k = ini + i + j se conserva. Los
invariantes son estables. ✓
Terminación
Cada vuelta escribe exactamente una posición,
así que el primer while termina: alguna copia se agota. En ese
momento, por I₁, lista[ini..k) contiene en orden los i + j menores;
los pendientes de la otra copia son los mayores y ya vienen ordenados,
y los dos while finales los escriben a continuación. lista[ini..fin]
queda completo y en orden: la poscondición. Los invariantes son
correctos. ∎
Así demuestra
CLRS la correctitud de su procedimiento Merge (pp. 31–33): con un
invariante de ciclo cuya estabilidad se revisa por casos. Las dos
técnicas del curso no compiten: la correctitud de la recursión se
argumenta por inducción estructural, y los invariantes certifican los
ciclos que quedan por dentro.
Teorema 2. La invocación mezclar(lista, ini, mitad, fin),
con los tramos lista[ini..mitad] y lista[mitad+1..fin] ordenados, deja
lista[ini..fin] ordenado con los mismos elementos que tenía.
Demostración: es trivial a partir de la correctitud de los
invariantes I₀ e I₁: al terminar los tres while, i = len(izq),
j = len(der) y k = fin + 1, y sustituir esos valores en I₁ da
lista[ini..fin] con todos los elementos de las dos copias, en orden,
que es la poscondición. ∎
6. El costo
Mezclar dos tramos con n elementos en total
cuesta: