Como pode mesclar dois arrays ordenados em um novo array ordenado, usando memória adicional para isso?

Para combinar dois arrays ordenados num novo array ordenado usando memória adicional, pode aplicar um algoritmo de fusão (merge), semelhante a um passo de ordenação por fusão.

Ideia:

1. Criar um novo array cujo tamanho seja a soma dos tamanhos dos dois arrays originais.
2. Usar dois ponteiros, um para cada array.
3. Comparar os elementos atuais de ambos os arrays, adicionar o menor ao novo array e mover o ponteiro correspondente.
4. Quando um dos arrays terminar, adicionar os elementos restantes do outro array.

Exemplo em 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 em tempo O(n + m), onde n e m são os tamanhos dos arrays, e usa memória adicional para o novo array.