Kako spojiti dva sortirana niza u novi sortirani niz koristeći dodatnu memoriju?

Da biste spojili dva sortirana niza u novi sortirani niz koristeći dodatnu memoriju, možete primeniti algoritam spajanja (merge), sličan koraku iz sortiranja spajanjem.

Ideja:

1. Kreirajte novi niz čija je veličina jednaka zbiru veličina dva originalna niza.
2. Koristite dva pokazivača, po jedan za svaki niz.
3. Upoređujte trenutne elemente oba niza, manji dodajte u novi niz i pomerite odgovarajući pokazivač.
4. Kada jedan od nizova završi, dodajte preostale elemente drugog niza.

Primer u 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
}

Ovaj algoritam radi u vremenu O(n + m), gde n i m predstavljaju veličine nizova, i koristi dodatnu memoriju za novi niz.