Как можете да обедините два сортирани масива в нов сортиран масив, използвайки допълнителна памет?

За да обедините два сортирани масива в нов сортиран масив с използване на допълнителна памет, можете да приложите алгоритъм за сливане (merge), подобен на стъпка от сортирането чрез сливане.

Идея:

1. Създайте нов масив, размерът на който е равен на сумата от размерите на двата изходни масива.
2. Използвайте два указателя — по един за всеки масив.
3. Сравнете текущите елементи на двата масива, по-малкият добавете към новия масив и преместете съответния указател.
4. Когато един от масивите приключи, добавете останалите елементи от другия масив.

Пример на 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 са размерите на масивите, и използва допълнителна памет за новия масив.