Kā var apvienot divus sakārtotus masīvus jaunā sakārtotā masīvā, izmantojot papildu atmiņu?

Lai apvienotu divus sakārtotus masīvus jauna sakārtota masīva veidā, izmantojot papildu atmiņu, var piemērot apvienošanas (merge) algoritmu, kas līdzīgs apvienošanas soļa izpildes secībai.

Ideja:

1. Izveidojiet jaunu masīvu, kura izmērs ir vienāds ar abu sākotnējo masīvu izmēru summu.
2. Izmantojiet divus rādītājus, pa vienam katram masīvam.
3. Salīdziniet abu masīvu pašreizējos elementus, mazāko pievienojiet jaunajam masīvam un pārvietojiet atbilstošo rādītāju.
4. Kad viens no masīviem beidzas, pievienojiet pārējos otra masīva elementus.

Piemērs Kotlin valodā (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 algoritms darbojas laikā O(n + m), kur n un m ir masīvu izmēri, un izmanto papildu atmiņu jaunajam masīvam.