Saltar a contenido

Divide y vencerás

Grupo A — viernes 21 de agosto de 2026, sesión virtual, de 9 a 11. Grupo B — viernes 28 de agosto de 2026.

Los dos grupos recibieron la misma sesión, con una semana de diferencia. Tuvo dos partes: un repaso del método de los invariantes, con el factorial y un ejercicio nuevo, y la primera técnica de diseño recursivo del curso: dividir, conquistar y combinar, con el máximo, el ordenamiento por mezcla y su recurrencia.

Diapositivas

Esta versión incluye lo que se anotó durante la clase, en las páginas donde apareció.

Repaso: la pareja de invariantes

Lo esencial de la clase del miércoles, condensado. Un problema se especifica con su entrada (las precondiciones) y su salida (las poscondiciones); una instancia es una entrada que cumple la precondición, y un algoritmo es correcto si calcula el resultado correcto para todas las instancias. Para los algoritmos iterativos la herramienta es el invariante: una propiedad sobre las variables que debe ser cierta a lo largo de la ejecución del ciclo. Vienen en pareja porque hay dos cosas que vigilar:

  • \(I_0\): las cotas del índice, que puede ser explícito o implícito. Si el ciclo es un for sobre los elementos, el índice no aparece en el código; usted lo asume como un contador de iteraciones que arranca en 0.
  • \(I_1\): qué lleva el acumulador en función del índice.

Si más variables cambian dentro del ciclo, la numeración continúa: \(I_2\), \(I_3\) y las que hagan falta. Y el método para demostrar que se cumplen tiene tres pasos: inicialización (la fórmula es verdadera antes de la primera iteración), estabilidad (si es cierta antes de cualquier iteración, sigue siéndolo después) y terminación (el ciclo termina y los invariantes entregan información sobre el objetivo del algoritmo).

El factorial, en acción

def fact(N):
    ans = 1
    i = 1
    while i <= N:
        ans = ans * i
        i = i + 1
    return ans

La recomendación de siempre para encontrar los invariantes: arranque con un valor, \(N = 5\), y mire la pareja \((i, \mathtt{ans})\) chequeo por chequeo:

\[(1, 1) \to (2, 1) \to (3, 2) \to (4, 6) \to (5, 24) \to (6, 120)\]

El patrón, generalizado: \(I_0: 1 \leq i \leq N+1\) e \(I_1: \mathtt{ans} = (i-1)!\). Se cumple en cada fila, con \(0! = 1\) salvando el arranque, y la cota \(N+1\) sale de la condición \(i \leq N\): el índice termina en el valor que la vuelve falsa.

De la demostración, que quedó anotada completa en las diapositivas, dos ideas para llevarse:

  • La estabilidad es un paso inductivo. Se asume que \(P(j)\) es cierto, los invariantes en la iteración \(i = j\), y se demuestra \(P(j+1)\), la siguiente. Es inducción matemática con otro nombre, y por eso la iteración que se toma es arbitraria y distinta de la última: de la última no hay siguiente que probar. El cálculo va por dos caminos que deben coincidir: el código dice \(\mathtt{ans} = (j-1)! \cdot j = j!\), y el invariante evaluado en \(j+1\) dice \(((j+1)-1)! = j!\). Coinciden. ✓
  • La terminación es una intersección. La condición rota da \(i > N\); el invariante \(I_0\) da \(i \leq N+1\). El único valor que cumple las dos cosas es \(i = N+1\), y ese es el valor con el que se evalúa \(I_1\): \(\mathtt{ans} = (N+1-1)! = N!\), la poscondición. Si esa intersección diera vacía o diera más de un valor, habría que revisar el algoritmo.

Teorema 2. fact(N) para cualquier \(N \geq 0\) produce \(N!\). Demostración: es trivial a partir de la correctitud de \(I_0\) e \(I_1\) (Teorema 1). \(\blacksquare\)

Otro ejercicio: la búsqueda

El segundo repaso fue la búsqueda lineal, con dos novedades. La primera: ans ya no acumula un valor numérico, acumula una respuesta, y su invariante es una fórmula con existencial, restringida al prefijo revisado:

\[I_0:\; 0 \leq i \leq N \qquad\qquad I_1:\; \mathtt{ans} = \exists\, p \in [0..i).\; A[p] = v\]

En la inicialización el existencial se evalúa sobre el rango \([0..0)\), que es vacío: no puede existir un \(p\) ahí, así que la fórmula vale falso, igual que ans. La segunda novedad: la estabilidad se parte por casos, según la posición examinada sea \(v\) o no. Ese esquema por casos reaparece hoy mismo en el ciclo de mezclar.

La pregunta de la clase: ¿y el invariante del arreglo?

En medio del repaso salió una pregunta que amerita respuesta escrita: si cada variable lleva su invariante, ¿no debería haber uno para el arreglo \(A\)?

La respuesta: el invariante habla de lo que cambia dentro del ciclo. En la búsqueda el arreglo solo se lee; no cambia, así que no hace parte del estado: es parte de la precondición, que es la que promete que llega un arreglo de números de tamaño \(N\). Pero si el algoritmo modificara el arreglo, una suma acumulada en sitio, un intercambio, cualquier escritura, entonces sí: el arreglo entra al estado y el invariante tiene que decir qué cumple.

De esa pregunta quedó el apéndice prometido en clase: tres ejercicios resueltos donde el arreglo se modifica y hace parte del invariante, incluido uno con dos ciclos anidados.

Validar invariantes en el código

Sobre los ejercicios resueltos apareció el truco de los assert: el invariante se escribe tal cual como una afirmación junto a la condición del ciclo, y si es falso en algún chequeo, el programa revienta ahí mismo y dice dónde. En Python es un assert directo; en Java tocaría lanzar una excepción cuando la condición no se cumpla. Los archivos de la nota de invariantes y del apéndice están construidos así.

Un problema para partir en dos

El máximo de un arreglo ya lo sabemos resolver, y certificar:

def maximo_iterativo(lista):
    mayor = lista[0]
    i = 1
    while i < len(lista):
        if lista[i] > mayor:
            mayor = lista[i]
        i = i + 1
    return mayor

Un ciclo que recorre las \(n\) posiciones, con \(I_0: 1 \leq i \leq n\) e \(I_1\): mayor es el máximo del prefijo recorrido. La pregunta que cambia el enfoque: ¿hay otra manera de pensar el problema, sin recorrerlo de izquierda a derecha?

La hay. Si alguien me dice el máximo de la mitad izquierda y el de la mitad derecha, el máximo total es el mayor de esos dos. Y cada mitad es el mismo problema, más pequeño: se resuelve igual, partiendo otra vez, hasta llegar a arreglos de un solo elemento.

El esquema divide y vencerás

Según CLRS (Sección 2.3.1), un algoritmo de divide y vencerás resuelve un problema de tamaño \(n\) en tres momentos:

  1. Dividir el problema en subproblemas más pequeños del mismo tipo.
  2. Conquistar cada subproblema resolviéndolo recursivamente; si es tan pequeño que resulta trivial, resolverlo directo: ese es el caso base.
  3. Combinar las soluciones parciales en la solución del problema original.

Para encontrar el caso base, échele cabeza a la pregunta ¿cuándo la solución es inmediata? Ordenar un arreglo: el de tamaño 1, porque ya está ordenado. El máximo: el de tamaño 1, porque es su propio máximo. Hasta ahí se divide.

¿Y la correctitud? Para los algoritmos recursivos la técnica es la inducción estructural: el caso base se verifica directo y el caso recursivo asume que las llamadas sobre problemas más pequeños son correctas. Es la pareja de los invariantes, que cubren los iterativos. La escritura completa de una de estas pruebas está en el apéndice.

El costo de un algoritmo de divide y vencerás queda descrito por una ecuación de recurrencia: si el problema de tamaño \(n\) se parte en \(a\) subproblemas de tamaño \(n/b\), y dividir más combinar cuesta \(f(n)\),

\[T(n) = a \cdot T(n/b) + f(n),\]

con el caso base costando constante, porque lo trivial cuesta constante. Los tres parámetros se leen del algoritmo: \(a \geq 1\) es cuántos subproblemas se generan, \(b > 1\) es en cuánto se reduce el tamaño por nivel, y \(f(n)\) es lo que cuesta partir y juntar.

El máximo, ahora recursivo

def maximo(lista, ini, fin):
    # Maximo de lista[ini..fin] partiendo el rango en dos
    if ini == fin:
        resultado = lista[ini]
    else:
        mitad = (ini + fin) // 2
        max_izq = maximo(lista, ini, mitad)
        max_der = maximo(lista, mitad + 1, fin)
        if max_izq >= max_der:
            resultado = max_izq
        else:
            resultado = max_der
    return resultado

Los tres momentos, en el código: dividir es calcular mitad; conquistar son las dos llamadas recursivas; combinar es el if final; y el caso base es el rango de un solo elemento. Un detalle que en clase se subrayó: la partición es por índices, nunca cortando la estructura de datos. Partir listas de verdad, copiando, es costoso; los índices ini y fin delimitan el rango sin mover un solo elemento.

¿Cuánto cuesta? Dos mitades, \(a = 2\) y \(b = 2\), y combinar es una sola comparación, \(f(n) = \Theta(1)\):

\[T(n) = 2\,T(n/2) + \Theta(1) \implies T(n) = O(n).\]

El ciclo también era \(O(n)\), así que partir el arreglo no hizo magia, y no podía hacerla: para hallar el máximo hay que mirar todos los elementos al menos una vez, ningún orden de visita baja de ahí. Lo que sí ganamos fue el forma de atacar el problema. La ganancia de verdad viene con el siguiente.

El ordenamiento por mezcla

Ordenar un arreglo grande es difícil. Pero suponga que las dos mitades ya vienen ordenadas: ¿qué tan fácil es juntarlas en una sola lista ordenada? Bastante, por una propiedad que se ve al ponerlas lado a lado: el menor de todos está al frente de una de las dos listas. Se toma, y se repite. Esa operación es la mezcla, y sobre ella se construye el ordenamiento.

La primera versión

La traducción directa del esquema es la que se le ocurre a uno primero: mezclar recibe dos listas y devuelve una lista nueva, y ordenar parte la lista con slices.

def mezclar(izq, der):
    # Combina dos listas ordenadas en una lista nueva
    resultado = []
    i = 0
    j = 0
    while i < len(izq) and j < len(der):
        if izq[i] <= der[j]:
            resultado.append(izq[i])
            i = i + 1
        else:
            resultado.append(der[j])
            j = j + 1
    while i < len(izq):
        resultado.append(izq[i])
        i = i + 1
    while j < len(der):
        resultado.append(der[j])
        j = j + 1
    return resultado

def ordenar(lista):
    # Ordena por mezcla: divide, conquista y combina
    if len(lista) <= 1:
        resultado = lista
    else:
        mitad = len(lista) // 2
        izq = ordenar(lista[0:mitad])
        der = ordenar(lista[mitad:len(lista)])
        resultado = mezclar(izq, der)
    return resultado

Funciona, y se escribe rápido. La pregunta que sigue es cuánto cuesta dividir así.

Lo que cuesta dividir copiando

lista[a:b] construye una lista nueva copiando sus \(b - a\) elementos uno por uno: tiempo y memoria \(\Theta(b-a)\). Dividir con slices convierte un paso que debía ser \(\Theta(1)\) en uno que cuesta \(\Theta(n)\), y la cuenta se resiente en cada algoritmo del curso:

  • En el máximo, la recurrencia pasaría de \(T(n) = 2\,T(n/2) + \Theta(1)\) a \(T(n) = 2\,T(n/2) + \Theta(n)\): de \(O(n)\) a \(O(n \lg n)\) solo por copiar al partir.
  • En la búsqueda binaria es peor: \(T(n) = T(n/2) + \Theta(1)\) da \(O(\lg n)\), y con slices \(T(n) = T(n/2) + \Theta(n)\) da \(O(n)\) — se pierde toda la gracia del algoritmo.
  • En el ordenamiento por mezcla el orden se salva, porque cada nivel ya paga \(\Theta(n)\) al mezclar; pero cada nivel copia otros \(n\) elementos solo para partir, y las celdas pedidas y liberadas suman \(\Theta(n \lg n)\).

Dividir debe ser gratis, y los índices lo logran: cada llamado dice de dónde a dónde trabaja, como ya lo hace maximo(lista, ini, fin). Lo que sigue es transformar esta versión, pieza por pieza.

La versión por índices

def ordenar(lista, ini, fin):
    # Ordena lista[ini..fin] en su lugar, partiendo el rango en dos
    if ini < fin:
        mitad = (ini + fin) // 2
        ordenar(lista, ini, mitad)
        ordenar(lista, mitad + 1, fin)
        mezclar(lista, ini, mitad, fin)
    return lista

Qué cambió: dividir ahora es calcular mitad, y los índices delimitan cada mitad sin mover un elemento, \(\Theta(1)\). El caso base quedó implícito: un rango de cero o un elemento (ini >= fin) no entra al if. Y mezclar ya no puede devolver una lista nueva: debe dejar el resultado en lista[ini..fin], el mismo tramo donde viven las dos mitades. El arreglo completo se ordena con ordenar(lista, 0, len(lista) - 1).

La mezcla, sobre el mismo arreglo

La mezcla recibe entonces los índices que delimitan los dos tramos ya ordenados, lista[ini..mitad] y lista[mitad+1..fin], y deja el tramo completo lista[ini..fin] ordenado. Antes de mezclar copia los dos tramos, y esa copia no es un capricho, como se ve en la traza de más abajo.

def mezclar(lista, ini, mitad, fin):
    # Combina los tramos ordenados lista[ini..mitad]
    # y lista[mitad+1..fin] sobre lista[ini..fin]
    izq = []
    der = []
    p = ini
    while p <= mitad:
        izq.append(lista[p])
        p = p + 1
    while p <= fin:
        der.append(lista[p])
        p = p + 1
    i = 0
    j = 0
    k = ini
    while i < len(izq) and j < len(der):
        if izq[i] <= der[j]:
            lista[k] = izq[i]
            i = i + 1
        else:
            lista[k] = der[j]
            j = j + 1
        k = k + 1
    while i < len(izq):
        lista[k] = izq[i]
        i = i + 1
        k = k + 1
    while j < len(der):
        lista[k] = der[j]
        j = j + 1
        k = k + 1
    return lista

La traza de la clase, ahora sobre el arreglo: mezclar(lista, 0, 2, 5) con lista = [2, 4, 7, 1, 3, 6]. Las copias quedan izq = [2, 4, 7] y der = [1, 3, 6], y cada vuelta escribe un elemento en la posición \(k\):

\(i\) \(j\) \(k\) Comparación lista tras escribir
0 0 0 \(2 > 1\): se escribe 1 [1, 4, 7, 1, 3, 6]
0 1 1 \(2 \leq 3\): se escribe 2 [1,2, 7, 1, 3, 6]
1 1 2 \(4 > 3\): se escribe 3 [1, 2,3, 1, 3, 6]
1 2 3 \(4 \leq 6\): se escribe 4 [1, 2, 3,4, 3, 6]
2 2 4 \(7 > 6\): se escribe 6 [1, 2, 3, 4,6, 6]
2 3 5 der agotada: se escribe 7 [1, 2, 3, 4, 6,7]

Vale la pena detenerse en la segunda fila: la escritura en \(k = 1\) tapa el \(4\) cuando el \(4\) todavía no ha salido. La mezcla sobrevive porque lee de las copias, nunca del tramo que está escribiendo; así construye CLRS su procedimiento Merge (p. 31), con los arreglos auxiliares \(L\) y \(R\). Cuando una copia se agota, los dos while finales escriben lo que queda de la otra, que ya viene ordenado y es mayor que todo lo escrito. Cada vuelta escribe exactamente un elemento y ninguno se escribe dos veces: mezclar dos tramos con \(n\) elementos en total cuesta \(\Theta(n)\) —contando las copias iniciales, que son otras \(n\) operaciones— y ese dato va a ser la clave del análisis.

El primer ciclo tiene su pareja de invariantes, como cualquier while:

\[I_0:\; 0 \leq i \leq \mathrm{len}(\mathtt{izq}) \;\wedge\; 0 \leq j \leq \mathrm{len}(\mathtt{der}) \;\wedge\; k = ini + i + j\]

e \(I_1\): lista[ini..k) contiene, en orden, los \(i + j\) elementos más pequeños de las dos copias. La estabilidad va por casos según cuál copia aporta el menor, el mismo esquema de la búsqueda del repaso. Así, con un invariante cuya estabilidad se revisa por casos, es como CLRS demuestra la correctitud de su procedimiento Merge (pp. 31--33); la escritura completa queda como ejercicio. Un detalle que conecta con el apéndice: aquí el arreglo se modifica, pero el invariante no necesita la cláusula de la zona intacta, porque el ciclo nunca lee de lista — todo lo que lee viene de las copias.

Con las dos piezas ya transformadas, el ordenamiento queda completo: los índices dividen y la mezcla combina sobre el mismo arreglo.

El árbol de llamadas es la figura 2.4 de CLRS, y en clase se dibujó con 16 elementos: partiendo quedan 2 de 8, luego 4 de 4, luego 8 de 2 y finalmente 16 de 1, el caso base. Son 5 niveles. La lectura es de ida y vuelta: bajar partiendo, subir mezclando. Al regreso, cada nivel junta dos arreglos ya ordenados, que es el escenario donde mezclar brilla.

¿Cuánto cuesta ordenar así?

Dos mitades, \(a = b = 2\), y combinar es la mezcla, que cuesta \(\Theta(n)\):

\[T(n) = 2\,T(n/2) + \Theta(n).\]

Para resolverla, el conteo por niveles del árbol. Un problema de tamaño \(n\), dos de \(n/2\), cuatro de \(n/4\), y así hasta los de tamaño 1. Cada nivel del árbol mueve, sumando todos sus pedazos, exactamente \(n\) elementos; y niveles hay \(\lg n + 1\). El total:

\[T(n) = n \, (\lg n + 1) \implies T(n) = O(n \lg n),\]

la cota de los buenos algoritmos de ordenamiento. La diferencia en la práctica es brutal: para un millón de elementos, un algoritmo cuadrático hace del orden de un billón de operaciones; el ordenamiento por mezcla, unos veinte millones. Ahí está la ganancia que el máximo no podía dar: la mezcla aprovecha el trabajo ya hecho por las dos mitades.

El método del árbol, en general

En clase quedó dibujada la expansión de la recurrencia, que es la manera sistemática de llegar a ese conteo. Escribiendo \(f(n) = c \cdot n\) para no pelear con la notación:

\[T(n) = 2\,T(n/2) + cn\]

se expande: el nivel 0 aporta \(cn\); el nivel 1, dos términos de \(c\,n/2\), que suman \(cn\); el nivel 2, cuatro de \(c\,n/4\), que suman \(cn\); y en general el nivel \(k\) tiene \(2^k\) pedazos de tamaño \(n/2^k\) que siempre suman \(cn\). ¿Hasta dónde? Hasta el caso base: \(n/2^k = 1\), o sea \(k = \log_2 n\). Niveles que suman \(cn\) cada uno, por \(\log_2 n + 1\) niveles:

\[T(n) = cn\,(\log_2 n + 1) = O(n \lg n).\]

La base del logaritmo no importa, porque cambiar de base es multiplicar por una constante y la notación asintótica las ignora. En las próximas sesiones se verán formas más rápidas de resolver recurrencias; por ahora, el árbol es el método.

El mismo conteo escrito como álgebra —sustituir la recurrencia dentro de sí misma, encontrar el patrón y resolver la sumatoria— está en el apéndice de recurrencias por expansión, con esta recurrencia y la del máximo desarrolladas paso a paso. Es la forma de justificar la cota cuando el enunciado pide la cuenta y no el dibujo.

Lo que ocupa en memoria

El tiempo no es lo único que hay que contar. mezclar construye las copias izquierda y derecha antes de escribir sobre el arreglo, así que el ordenamiento por mezcla no es in situ: no reorganiza la estructura que recibe, produce valores nuevos.

Para saber cuánto pesa eso hay que mirar qué está vivo al mismo tiempo. Las dos llamadas recursivas no corren a la vez: ordenar de la mitad izquierda termina por completo antes de que arranque la de la derecha. En el momento más profundo, entonces, lo que está abierto es una sola rama del árbol, desde la raíz hasta la hoja: \(\lg n + 1\) marcos. El marco de profundidad \(i\) trabaja sobre un tramo de \(n/2^i\) elementos y sus copias suman eso mismo, así que el total vivo es

\[n + \frac{n}{2} + \frac{n}{4} + \cdots + 1 = 2n - 1 = \Theta(n).\]

Memoria adicional \(\Theta(n)\), más los \(\Theta(\lg n)\) marcos que la sostienen. Esa es la razón de fondo por la que el ordenamiento por mezcla es la referencia de los cursos y no la de las bibliotecas: ordena en \(\Theta(n \lg n)\) garantizado, pero pide un arreglo entero de espacio prestado. El quicksort, que llega más adelante, ordena in situ —sus marcos guardan índices, no copias— y por eso se lo prefiere en la práctica, aun cuando su peor caso es \(\Theta(n^2)\).

La anatomía de un algoritmo de divide y vencerás

Estos algoritmos suelen tener dos funciones:

  • La que combina (mezclar): recibe dos o más soluciones parciales que ya cumplen la propiedad de solución (aquí, los tramos vienen ordenados; en el máximo, ser el máximo de su parte) y produce una solución del problema mayor que cumple la misma propiedad.
  • La que divide y llama (ordenar): trae el caso base con su solución trivial, la partición, las llamadas recursivas y la combinación.

A veces la parte de combinar no existe, porque el propio conquistar deja resuelto el problema; el quicksort, que aparecerá más adelante, es el ejemplo clásico. Pero la mayoría de los algoritmos de esta familia tienen las dos partes.

Cuando un while vive adentro de otro, cada uno lleva su propia pareja de invariantes, la del interno continuando la numeración (\(I_2\), \(I_3\)). El apéndice trae un ejemplo completo.

Errores comunes

  • Caso base ausente o mal puesto. La recursión nunca toca fondo y el paso de terminación no tiene de dónde agarrarse.
  • Una partición que no reduce. Si una de las partes puede quedar del tamaño original, el algoritmo se cuelga, igual que un ciclo sin terminación.
  • Mezclar olvidando los sobrantes. Cuando una copia se agota, lo que queda de la otra debe escribirse: los dos while finales de mezclar no son de adorno.
  • Equivocar \(f(n)\) en la recurrencia. La mezcla cuesta \(\Theta(n)\), no \(\Theta(1)\); con la \(f(n)\) errada, el análisis entero da otro valor.

El costo escondido de lista[i]

Hay un segundo costo, más discreto, que sí se tolera. Una lista de Python no es un arreglo compacto: guarda referencias a objetos que viven repartidos por la memoria, así que cada lista[i] paga una indirección que un arreglo de C o de C++ no paga.

Ese sobrecosto es un factor constante: lista[i] sigue siendo \(O(1)\), el análisis asintótico no se mueve y por eso el curso trabaja con listas de Python sin remordimiento. Las copias de los slices son otra historia: agregan trabajo \(\Theta(n)\) donde la división debía ser gratis, y eso sí cambia la cuenta.

Ejercicios

  1. Escriba un algoritmo de divide y vencerás que calcule la suma de un arreglo. Plantee su recurrencia y estime el costo.
  2. Escriba un algoritmo de divide y vencerás que cuente cuántas veces aparece un valor en un arreglo.
  3. Usando \(b^n = (b^{n/2})^2\) cuando \(n\) es par, diseñe un algoritmo para calcular \(b^n\). Plantee una recurrencia como \(T(n) = T(n/2) + 1\) y expanda algunos niveles: ¿a qué cota llega?
  4. Para el primer ciclo de mezclar: demuestre la inicialización y la estabilidad de sus invariantes \(I_0\) e \(I_1\), y use la terminación para concluir que la mezcla es correcta. La estabilidad se parte en dos casos, según cuál copia aporta el menor; en cada uno, diga qué exige el invariante evaluado en el nuevo valor y por qué el estado que dejó el código lo cumple.

Ejercicios interactivos

Los dos de divide y vencerás se recorrieron en clase y están en la página de ejercicios interactivos:

  • mezclar — ejecute la mezcla escritura por escritura sobre el arreglo, proponga la pareja de invariantes del primer while y arme la demostración completa, con la estabilidad por casos.
  • ordenar — el ordenamiento por mezcla dibujado completo: baje partiendo la lista nivel por nivel hasta el caso base y súbala mezclando. La tabla acumula el trabajo por nivel y ahí aparece el patrón del \(n \lg n\); con 16 elementos, los 5 niveles del tablero.

Los de invariantes, sumar y factorial, siguen disponibles para el repaso.

Lo que queda pendiente

La escritura formal de la inducción estructural y los ciclos anidados se trabajan con el profesor titular. El apéndice trae la prueba del máximo recursivo escrita completa y un ejercicio de dos ciclos con sus dos parejas de invariantes. El material de divide y vencerás del profesor en su página, incluido el del semestre pasado, cubre lo mismo que esta introducción y es la referencia para el estilo de los parciales.

Referencias

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, 3.ª ed., MIT Press, 2009. Sección 2.3, pp. 30--37: divide y vencerás, el procedimiento Merge con su invariante (pp. 31--33) y la figura 2.4 con el árbol del ordenamiento por mezcla.
  • C. Rocha. Diseño y Análisis de Algoritmos. Está en la biblioteca.