py_merge_sorted_lists · Python

▶ Aprender py_merge_sorted_lists (Python) paso a paso · explicación de py_merge_sorted_lists

Código línea a línea

Tres columnas: el código, el trozo del subject o del main que obliga a escribir esa línea, y el por qué.

py_merge_sorted_lists.py

Código	Subject	Por qué
`def merge_sorted_lists(lists: list[list[int]]) -> list[int]:`	`def merge_sorted_lists(lists: list[list[int]]) -> list[int]:`	Firma del subject.
`pending = [lst for lst in lists if lst]`	Empty lists should be ignored during merging	Me quedo con las listas no vacías.
`if not pending:`	Return empty list if no valid input is provided	Nada que mezclar: entrada vacía o solo listas vacías.
`return []`		Vacía.
`while len(pending) > 1:`	Maintain optimal efficiency for large inputs	Mezclo por parejas hasta que quede una. Cada ronda recorre todos los elementos una vez y reduce el número de listas a la mitad: O(N log k), lo mismo que con `heapq`.
`pending = [merge_two(pending[i], pending[i + 1]) if i + 1 < len(pending) else pending[i]`	merges multiple sorted lists into one sorted list	Pareja a pareja. Si el número es impar, la última pasa sola a la siguiente ronda.
`for i in range(0, len(pending), 2)]`		De dos en dos.
`return list(pending[0])`	Single list input: return copy of that list	`list(...)` por si solo había una lista: devuelvo copia, no la misma referencia.


`def merge_two(a, b):`		La mezcla de dos listas ordenadas de toda la vida (es `py_shadow_merge`).
`merged = []`		Resultado.
`i = j = 0`		Un puntero por lista.
`while i < len(a) and j < len(b):`		Mientras queden en ambas.
`if b[j] < a[i]:`	Handle negative numbers correctly	Comparación con `<` normal: los negativos no necesitan nada especial.
`merged.append(b[j])`		Va la de `b`.
`j += 1`		Avanzo.
`else:`	Preserve duplicates across different lists	Menor o igual: va la de `a`. En empate no descarto nada, así se conservan los duplicados.
`merged.append(a[i])`		Va la de `a`.
`i += 1`		Avanzo.
`merged.extend(a[i:])`		El resto de la que no se agotó.
`merged.extend(b[j:])`		Solo una tendrá resto.
`return merged`		Ordenada.