Ako spojiť dva zoradené polia do nového zoradeného poľa s použitím dodatočej pamäte?

Ak chcete spojiť dve zoradené polia do nového zoradeného poľa s použitím dodatočej pamäte, môžete použiť algoritmus zlučovania (merge), podobný kroku zo zlučovania triedenia.

Myšlienka:

1. Vytvorte nové pole, ktorého veľkosť je rovná súčtu veľkostí oboch pôvodných polí.
2. Použite dva ukazovatele, jeden pre každý pole.
3. Porovnajte aktuálne prvky oboch polí, pridajte menší do nového poľa a posuňte príslušný ukazovateľ.
4. Keď jeden z polí skončí, pridajte zostávajúce prvky druhého poľa.

Príklad v 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
}

Tento algoritmus funguje v čase O(n + m), kde n a m sú veľkosti polí, a používa dodatočnú pamäť pre nový pole.