Come si possono unire due array ordinati in un nuovo array ordinato, utilizzando memoria aggiuntiva?

Per unire due array ordinati in un nuovo array ordinato utilizzando memoria aggiuntiva, è possibile applicare un algoritmo di fusione (merge), simile a un passo del merge sort.

Idea:

1. Creare un nuovo array di dimensione uguale alla somma delle dimensioni dei due array originali.
2. Usare due puntatori, uno per ciascun array.
3. Confrontare gli elementi correnti di entrambi gli array, aggiungere il più piccolo al nuovo array e spostare il puntatore corrispondente.
4. Quando uno degli array termina, aggiungere gli elementi rimanenti dell'altro array.

Esempio in 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
}

Questo algoritmo funziona in tempo O(n + m), dove n e m sono le dimensioni degli array, e utilizza memoria aggiuntiva per il nuovo array.