Kuidas saab kahe sorteeritud massiivi ühendada uueks sorteeritud massiiviks, kasutades selleks täiendavat mälu?

Kaks järjestatud massiivi ühendamiseks uueks järjestatud massiiviks, kasutades täiendavat mälu, saab rakendada ühendamise (merge) algoritmi, mis sarnaneb merge sort'i sammu või osaga.

Idee:

1. Loo uus massiiv, mille suurus on võrdne kahe algse massiivi suuruste summaga.
2. Kasuta kahte näidikut, ühe iga massiivi jaoks.
3. Võrdle mõlema massiivi praeguseid elemente, väiksemat lisa uude massiivi ja liigu vastava näidiku suunas.
4. Kui üks massiividest lõpeb, lisa ülejäänud teise massiivi elemendid.

Näide Kotlinis (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
}

See algoritm töötab O(n + m) ajal, kus n ja m on massiivide suurused, ning kasutab täiendavat mälu uue massiivi jaoks.