Jak lze spojit dva seřazené pole do nového seřazeného pole s použitím dodatečné paměti?

Pro spojení dvou seřazených polí do nového seřazeného pole s použitím dodatečné paměti lze použít algoritmus sloučení (merge), podobný kroku ze sloučení řazení.

Nápad:

1. Vytvořte nové pole, jehož velikost je rovna součtu velikostí obou původních polí.
2. Použijte dva ukazatele, jeden pro každé pole.
3. Porovnejte aktuální prvky obou polí, přidejte menší do nového pole a posuňte odpovídající ukazatel.
4. Když jedno z polí skončí, přidejte zbývající prvky druhého pole.

Pří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 pracuje v čase O(n + m), kde n a m jsou velikosti polí, a používá dodatečnou paměť pro nové pole.