How can two sorted arrays be merged into a new sorted array using additional memory?

To merge two sorted arrays into a new sorted array using additional memory, you can apply a merge algorithm similar to the merge step in merge sort.

Idea:

1. Create a new array with a size equal to the sum of the sizes of the two original arrays.
2. Use two pointers — one for each array.
3. Compare the current elements of the two arrays, add the smaller one to the new array, and move the corresponding pointer.
4. When one of the arrays is exhausted, add the remaining elements of the other array.

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

This algorithm runs in O(n + m) time, where n and m are the sizes of the arrays, and uses additional memory for the new array.