Cómo fusionar dos arrays ordenados sin memoria extra

¿Cómo combinar dos arrays ordenados en uno solo manteniendo el orden ascendente? Ese es el reto del problema Merge Two Sorted Lists, un ejercicio clásico para practicar manipulación de arrays, complejidad temporal y pensamiento algorítmico antes de escribir una sola línea de código.

¿Qué pide el problema Merge Two Sorted Lists?

El enunciado entrega cuatro entradas y pide devolver un único array ordenado de forma ascendente.

Las entradas son dos listas de enteros, nums1 y nums2, junto con dos enteros, m y n, que representan cuántos elementos válidos hay en cada lista. Ambas listas vienen ya ordenadas de forma independiente, así que tu trabajo es fusionarlas sin romper ese orden [00:23].

¿Qué significa que nums1 tenga longitud m+n? Que el array más grande reserva espacio para todos los elementos finales. Los primeros m valores son reales y los últimos n son ceros que debes ignorar.

¿Por qué nums1 trae ceros al final?

Esa es la parte que suele confundir al leer el problema por primera vez.

Si nums1 tiene cuatro elementos válidos y nums2 tiene tres, nums1 llega con longitud siete: cuatro números reales y tres ceros de relleno. Esos ceros no son datos, son espacio reservado para acomodar los valores de nums2 cuando hagas la fusión [01:00].

Piénsalo como una caja con compartimentos vacíos esperando ser llenados. No tienes que crear un array nuevo, tienes que aprovechar el que ya viene preparado.

¿Cómo abordar la solución antes de programar?

Antes de escribir código, conviene dibujar el flujo y pensar en la complejidad.

Este tipo de problemas premia a quien planea. Si te lanzas a teclear sin diagramar, terminas con bucles anidados innecesarios o estructuras auxiliares que disparan el uso de memoria. La recomendación es clara: primero diagrama, después implementa [01:30].

• Identifica qué representa cada variable de entrada.
• Dibuja en papel cómo se vería la fusión paso a paso.
• Estima la complejidad temporal y espacial de tu enfoque.

Después de ese ejercicio, recién ahí abres el editor.

¿Qué es la complejidad temporal y espacial en este reto?

Son las dos métricas con las que se mide la calidad de tu solución.

¿Qué es la complejidad temporal? Mide cuántas operaciones hace tu algoritmo en función del tamaño de la entrada. En este problema, lo ideal es lograr O(m+n).

¿Qué es la complejidad espacial? Mide cuánta memoria adicional necesita tu algoritmo. Si fusionas en el mismo nums1 sin crear listas nuevas, tu costo espacial es O(1).

Lograr ambas métricas óptimas es el objetivo cuando enfrentas un merge de arrays ordenados.

¿Qué entrada de ejemplo recibe el algoritmo?

Un caso típico entrega nums1 con sus valores reales seguidos de ceros, nums2 con sus valores y los enteros m y n indicando los conteos.

La salida esperada es una sola lista con todos los números ordenados de menor a mayor. No hay que devolver índices ni estructuras adicionales, solo el array fusionado [01:15].

El reto está en hacerlo con el menor costo posible de tiempo y memoria. ¿Qué complejidad temporal y espacial alcanzaste tú? Comenta tu enfoque antes de ver la solución en la próxima clase.