py_merge_sorted_lists

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

Entregas: py_merge_sorted_lists.py con merge_sorted_lists(lists). Rank 04 · nivel 2.

Qué pide (en palabras normales)

Subject (enunciado original)
Write a function that merges multiple sorted lists into one sorted list while maintaining the sort order efficiently.

The function should:
- Take a list of sorted integer lists as input
- Return a single merged list in ascending order
- Preserve all duplicate elements in the final result
- Handle empty lists and empty input gracefully
- Maintain optimal efficiency for large inputs

Rules:
- All input lists are guaranteed to be sorted in ascending order
- Empty lists should be ignored during merging
- Return empty list if no valid input is provided
- Preserve duplicates across different lists
- Handle negative numbers correctly

Edge cases to handle:
- Empty input list: return empty list
- Lists containing only empty lists: return empty list
- Single list input: return copy of that list
- All duplicate elements: preserve all instances
- Negative numbers: handle correctly in sort order

Expected file: py_merge_sorted_lists.py
Function signature:
def merge_sorted_lists(lists: list[list[int]]) -> list[int]:
Forbidden: sorted(), .sort(), heapq.merge()

Examples:
merge_sorted_lists([[1, 3, 5], [2, 4, 6]])
=> [1, 2, 3, 4, 5, 6]
merge_sorted_lists([[1, 5, 9], [2, 3, 8], [4, 6, 7]])
=> [1, 2, 3, 4, 5, 6, 7, 8, 9]
merge_sorted_lists([[5], [1, 3], [2, 4]])
=> [1, 2, 3, 4, 5]
merge_sorted_lists([[1, 1, 2], [2, 3, 3]])
=> [1, 1, 2, 2, 3, 3]
merge_sorted_lists([[], [1, 2, 3]])
=> [1, 2, 3]
merge_sorted_lists([[]])
=> []
merge_sorted_lists([[-5, -1, 0], [-3, 2, 4]])
=> [-5, -3, -1, 0, 2, 4]
merge_sorted_lists([[10], [10], [10]])
=> [10, 10, 10]

Mezcla por parejas

pending = [lst for lst in lists if lst]
while len(pending) > 1:
    pending = [merge_two(pending[i], pending[i + 1]) if i + 1 < len(pending) else pending[i]
               for i in range(0, len(pending), 2)]
return list(pending[0])

Con k listas: mezclo la 1 con la 2, la 3 con la 4... y repito con las que salen. Cada ronda toca todos los elementos una vez y hay log k rondas. Es la misma complejidad que el heap, sin importar nada.

Por qué no mezclar en cadena

result = merge_two(result, lst) para cada lista también funciona, pero recorre result entero en cada paso: O(N·k). El subject dice "optimal efficiency for large inputs" y el corrector puede meter muchas listas.

merge_two

Es py_shadow_merge de rank 03 tal cual: dos punteros, el menor sale, y el resto se pega al final.

Trampas