Чтобы объединить два отсортированных массива в новый отсортированный массив с использованием дополнительной памяти, можно применить алгоритм слияния (merge), похожий на шаг из сортировки слиянием.

Идея:

Создаем новый массив, размер которого равен сумме размеров двух исходных.
Используем два указателя — по одному для каждого массива.
Сравниваем текущие элементы двух массивов, меньший добавляем в новый массив и сдвигаем соответствующий указатель.
Когда один из массивов заканчивается, добавляем оставшиеся элементы другого массива.

Пример на 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
}

Этот алгоритм работает за время O(n + m), где n и m — размеры массивов, и использует дополнительную память для нового массива.

Каким образом можно объединить два отсортированных массива в новый отсортированный массив, используя для этого дополнительную память?