¿Cómo se pueden combinar dos arreglos ordenados en un nuevo arreglo ordenado, utilizando memoria adicional para ello?

Para combinar dos arreglos ordenados en un nuevo arreglo ordenado usando memoria adicional, se puede aplicar un algoritmo de fusión (merge), similar a un paso del ordenamiento por fusión.

Idea:

1. Crear un nuevo arreglo cuyo tamaño sea la suma de los tamaños de los dos arreglos originales.
2. Usar dos punteros, uno para cada arreglo.
3. Comparar los elementos actuales de ambos arreglos, agregar el menor al nuevo arreglo y mover el puntero correspondiente.
4. Cuando uno de los arreglos termine, agregar los elementos restantes del otro arreglo.

Ejemplo en Kotlin (Android):

fun mergeSortedArrays(arr1: IntArray, arr2: IntArray): IntArray {
    val result = IntArray(arr1.size + arr2.size)
    var i = 0
    var j = 0
    var k = 0

    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++]
        } else {
            result[k++] = arr2[j++]
        }
    }

    while (i < arr1.size) {
        result[k++] = arr1[i++]
    }

    while (j < arr2.size) {
        result[k++] = arr2[j++]
    }

    return result
}

Este algoritmo funciona en tiempo O(n + m), donde n y m son los tamaños de los arreglos, y usa memoria adicional para el nuevo arreglo.