Cum se pot combina două array-uri sortate într-unul nou sortat, folosind memorie suplimentară?

Pentru a combina două array-uri sortate într-un nou array sortat folosind memorie suplimentară, se poate aplica un algoritm de fuziune (merge), similar cu un pas din sortarea prin fuziune.

Ideea:

1. Creăm un nou array a cărui dimensiune este egală cu suma dimensiunilor celor două array-uri inițiale.
2. Folosim doi indicatori, câte unul pentru fiecare array.
3. Comparăm elementele curente ale ambelor array-uri, adăugăm pe cel mai mic în noul array și mutăm indicatorul corespunzător.
4. Când unul dintre array-uri se termină, adăugăm elementele rămase ale celuilalt array.

Exemplu în 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
}

Acest algoritm funcționează în timp O(n + m), unde n și m sunt dimensiunile array-urilor, și folosește memorie suplimentară pentru noul array.