Kaip galima sujungti du surūšiuotus masyvus į naują surūšiuotą masyvą, naudojant papildomą atmintį?

Norint sujungti du surūšiuotus masyvus į naują surūšiuotą masyvą naudojant papildomą atmintį, galima taikyti sujungimo (merge) algoritmą, panašų į žingsnį iš sujungimo rūšiavimo.

Idėja:

1. Sukurkite naują masyvą, kurio dydis yra lygus dviejų pradinio masyvo dydžių sumai.
2. Naudokite du rodyklius, po vieną kiekvienam masyvui.
3. Palyginkite dabartinius abiejų masyvų elementus, mažesnį įtraukite į naują masyvą ir perjunkite atitinkamą rodyklį.
4. Kai vienas iš masyvų baigiasi, įtraukite likusius kito masyvo elementus.

Pavyzdys Kotlin kalba (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
}

Šis algoritmas veikia laiku O(n + m), kur n ir m yra masyvų dydžiai, ir naudoja papildomą atmintį naujam masyvui.