¿Cómo se pueden combinar dos secuencias ordenadas de manera que el resultado siga estando ordenado?

Para combinar dos secuencias ordenadas en una sola ordenada, se puede usar el algoritmo de fusión (merge), que funciona en tiempo lineal.

Idea:

• Hay dos arreglos o listas ordenadas.
• Usamos dos punteros, uno para cada arreglo.
• Comparamos los elementos actuales, el menor se añade al resultado y desplazamos el puntero correspondiente.
• Repetimos hasta recorrer ambos arreglos.

Ejemplo en Kotlin:

fun mergeSortedLists(a: List<Int>, b: List<Int>): List<Int> {
    val result = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < a.size && j < b.size) {
        if (a[i] <= b[j]) {
            result.add(a[i])
            i++
        } else {
            result.add(b[j])
            j++
        }
    }
    // Añadimos los elementos restantes
    while (i < a.size) result.add(a[i++])
    while (j < b.size) result.add(b[j++])
    return result
}