← Volver a los ejercicios

mezclar: dos tramos ordenados en uno

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ónklista

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. ∎
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: