Wie kann man zwei sortierte Arrays mit zusätzlichem Speicher in ein neues sortiertes Array zusammenführen?

Um zwei sortierte Arrays in ein neues sortiertes Array mit zusätzlichem Speicher zu kombinieren, kann man einen Merge-Algorithmus anwenden, ähnlich einem Schritt des Mergesort.

Idee:

1. Erstellen Sie ein neues Array, dessen Größe der Summe der Größen der beiden ursprünglichen Arrays entspricht.
2. Verwenden Sie zwei Zeiger, einen für jedes Array.
3. Vergleichen Sie die aktuellen Elemente beider Arrays, fügen Sie das kleinere in das neue Array ein und verschieben Sie den entsprechenden Zeiger.
4. Wenn eines der Arrays endet, fügen Sie die verbleibenden Elemente des anderen Arrays hinzu.

Beispiel 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
}

Dieser Algorithmus läuft in O(n + m) Zeit, wobei n und m die Größen der Arrays sind, und verwendet zusätzlichen Speicher für das neue Array.