Jak można połączyć dwie posortowane tablice w nową posortowaną tablicę, używając dodatkowej pamięci?

Aby połączyć dwie posortowane tablice w nową posortowaną tablicę z użyciem dodatkowej pamięci, można zastosować algorytm scalania (merge), podobny do kroku sortowania przez scalanie.

Pomysł:

1. Utwórz nową tablicę o rozmiarze równym sumie rozmiarów dwóch oryginalnych tablic.
2. Użyj dwóch wskaźników — po jednym dla każdej tablicy.
3. Porównaj bieżące elementy obu tablic, dodaj mniejszy do nowej tablicy i przesuwaj odpowiedni wskaźnik.
4. Gdy jedna z tablic się skończy, dodaj pozostałe elementy drugiej tablicy.

Przykład w 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
}

Ten algorytm działa w czasie O(n + m), gdzie n i m to rozmiary tablic, i używa dodatkowej pamięci na nową tablicę.