SolveConPython

Python Reto #16 — Merge de dos listas ordenadas

Nivel: Intermedio
Tema: Algoritmos básicos, “dos punteros”, eficiencia, validación de entradas, tests con pytest
Objetivo: Combinar dos listas ya ordenadas en una sola lista ordenada, en tiempo lineal, sin usar sorted() sobre la lista completa.

Enunciado

Crea una función llamada merge_listas_ordenadas(a, b) que:

  1. Reciba dos valores a y b.
  2. Si a o b es None, trate ese valor como lista vacía.
  3. Si a o b no es una lista (list), lance TypeError.
  4. Asuma que ambas listas están ordenadas de menor a mayor.
  5. Devuelva una nueva lista que contenga todos los elementos de a y b, también ordenada.
  6. No use sorted() ni .sort() para resolver el problema completo.
    (La idea es practicar el algoritmo de merge en O(n + m).)

Para este reto, asume que los elementos son comparables entre sí (por ejemplo, todos números).

Ejemplos

  • merge_listas_ordenadas([1, 3, 5], [2, 4, 6]) → [1, 2, 3, 4, 5, 6]
  • merge_listas_ordenadas([1, 2, 2], [2, 3]) → [1, 2, 2, 2, 3]
  • merge_listas_ordenadas([], [1, 2]) → [1, 2]
  • merge_listas_ordenadas(None, [1]) → [1]
  • merge_listas_ordenadas("123", [1]) → TypeError

Pistas

  1. Usa dos índices: i para a, j para b.
  2. Compara a[i] con b[j] y añade el menor al resultado.
  3. Avanza el índice del que tomaste el elemento.
  4. Al final, añade lo que quede de la lista que aún tenga elementos.

Solución explicada (paso a paso)

  1. Si a o b es None, lo convertimos a [].
  2. Validamos que ambos sean listas.
  3. Inicializamos:
    • i = 0, j = 0
    • resultado = []
  4. Mientras queden elementos en ambas listas:
    • añadimos el menor de a[i] y b[j]
    • avanzamos i o j
  5. Añadimos el resto de la lista que aún tenga elementos.
  6. Devolvemos resultado.

Ejecuta:

  • pytest -q

Variantes para subir de nivel (opcional)

  1. Merge descendente (de mayor a menor)
  2. Merge de listas de diccionarios por una clave (ej. "fecha")
  3. Detectar si las listas no están ordenadas y lanzar error (validación extra)
  4. Implementar “merge generator” (yield) para streaming

Lo que aprendiste

  • El patrón de “dos punteros”
  • Cómo lograr O(n+m) sin ordenar de nuevo
  • Manejo de duplicados preservando orden
  • Tests para algoritmos deterministas

Accede al código completo y a los tests en GitHub para ejecutar y modificar la solución localmente.

Continúa con Reto #17 — Contar ocurrencias con collections.Counter (comparativa) para aprender cuándo simplificar código usando la librería estándar sin perder claridad.