Hoe kunnen twee gesorteerde arrays worden samengevoegd tot een nieuwe gesorteerde array, met behulp van extra geheugen?

Om twee gesorteerde arrays samen te voegen tot een nieuwe gesorteerde array met behulp van extra geheugen, kan een merge-algoritme worden toegepast, vergelijkbaar met een stap uit de merge sort.

Idee:

1. Maak een nieuwe array waarvan de grootte gelijk is aan de som van de groottes van de twee oorspronkelijke arrays.
2. Gebruik twee pointers, één voor elk array.
3. Vergelijk de huidige elementen van beide arrays, voeg de kleinste toe aan de nieuwe array en verplaats de bijbehorende pointer.
4. Wanneer een van de arrays eindigt, voeg dan de resterende elementen van de andere array toe.

Voorbeeld in 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
}

Dit algoritme werkt in O(n + m) tijd, waarbij n en m de groottes van de arrays zijn, en gebruikt extra geheugen voor de nieuwe array.