Hogyan lehet két rendezett tömböt egy új rendezett tömbbé összefűzni extra memória felhasználásával?

Két rendezett tömb egyesítése további memória használatával egy új rendezett tömbbe, alkalmazhatunk egy összeolvasztási (merge) algoritmust, amely hasonló a merge sort egyik lépéséhez.

Ötlet:

1. Hozzunk létre egy új tömböt, amelynek mérete megegyezik a két eredeti tömb méretének összegével.
2. Használjunk két mutatót, egyet mindkét tömbhöz.
3. Hasonlítsuk össze a két tömb aktuális elemeit, a kisebbet adjuk hozzá az új tömbhöz, és mozgassuk a megfelelő mutatót.
4. Amikor az egyik tömb véget ér, adjuk hozzá a másik többi elemét.

Példa Kotlinban (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
}

Ez az algoritmus O(n + m) időben működik, ahol n és m az array-ek méretei, és extra memóriát használ az új array számára.