SolveConPython

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.

def merge_listas_ordenadas(a: list | None, b: list | None) -> list:
    """
    Une dos listas ordenadas en una sola lista ordenada (merge) en O(n+m).
    Reglas:
    - Si a o b es None -> se trata como []
    - a y b deben ser list
    - No usar sorted() / sort() para resolver el merge completo
    """
    if a is None:
        a = []
    if b is None:
        b = []
    if not isinstance(a, list) or not isinstance(b, list):
        raise TypeError("Los parámetros 'a' y 'b' deben ser listas (list) o None.")
    i = 0
    j = 0
    resultado = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            resultado.append(a[i])
            i += 1
        else:
            resultado.append(b[j])
            j += 1
    if i < len(a):
        resultado.extend(a[i:])
    if j < len(b):
        resultado.extend(b[j:])
    return resultado

import pytest
from reto_16_merge_listas_ordenadas import merge_listas_ordenadas
def test_merge_basico():
    assert merge_listas_ordenadas([1, 3, 5], [2, 4, 6]) == [1, 2, 3, 4, 5, 6]
def test_merge_con_duplicados():
    assert merge_listas_ordenadas([1, 2, 2], [2, 3]) == [1, 2, 2, 2, 3]
def test_una_lista_vacia():
    assert merge_listas_ordenadas([], [1, 2]) == [1, 2]
def test_none_como_lista_vacia():
    assert merge_listas_ordenadas(None, [1]) == [1]
    assert merge_listas_ordenadas([1], None) == [1]
    assert merge_listas_ordenadas(None, None) == []
def test_tipo_incorrecto_lanza_typeerror():
    with pytest.raises(TypeError):
        merge_listas_ordenadas("123", [1])

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.