py_shadow_merge

Código comentado línea a línea y paso a paso:

• Python · paso a paso

Entregas: py_shadow_merge.py con shadow_merge(list1, list2). Rank 03 · nivel 4.

Qué pide (en palabras normales)

• Dos listas ya ordenadas → una ordenada con todo. El paso de mezcla del merge sort.

Write a function that merges two sorted lists into one sorted list.

Expected file: py_shadow_merge.py
Function signature:
def shadow_merge(list1: list[int], list2: list[int]) -> list[int]:

Examples:
shadow_merge([1,3,5], [2,4,6])
=> [1,2,3,4,5,6]
shadow_merge([1,2,3], [4,5,6])
=> [1,2,3,4,5,6]
shadow_merge([1], [2,3,4])
=> [1,2,3,4]
shadow_merge([], [1,2,3])
=> [1,2,3]
shadow_merge([1,1,2], [1,3,3])
=> [1,1,1,2,3,3]

Solución: dos punteros

while i < len(list1) and j < len(list2):
    if list2[j] < list1[i]:
        merged.append(list2[j])
        j += 1
    else:
        merged.append(list1[i])
        i += 1
merged.extend(list1[i:])
merged.extend(list2[j:])

Comparo las cabezas, saco la menor, avanzo. Cuando una se agota, el resto de la otra va entero. Lineal.

¿Y sorted(list1 + list2)?

Pasa los tests y aquí no está prohibido. Pero es O(n log n) y no aprovecha que ya vienen ordenadas; si el examen te pone este ejercicio es para que escribas la mezcla. En py_merge_sorted_lists (rank 04) es el mismo problema con sorted prohibido: aprende la versión de punteros y la reutilizas.

Trampas

• No olvides los extend finales: sin ellos pierdes la cola de la lista más larga.
• No hagas list1.pop(0): muta la entrada (el corrector lo detecta) y es O(n) por pop.