Comment peut-on fusionner deux tableaux triés en un nouveau tableau trié, en utilisant de la mémoire supplémentaire ?

Pour fusionner deux tableaux triés en un nouveau tableau trié en utilisant de la mémoire supplémentaire, vous pouvez appliquer un algorithme de fusion (merge), similaire à une étape du tri par fusion.

Idée:

1. Créer un nouveau tableau dont la taille est la somme des tailles des deux tableaux d'origine.
2. Utiliser deux pointeurs, un pour chaque tableau.
3. Comparer les éléments actuels des deux tableaux, ajouter le plus petit au nouveau tableau et déplacer le pointeur correspondant.
4. Lorsque l'un des tableaux est terminé, ajouter les éléments restants de l'autre tableau.

Exemple en 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
}

Ce algorithme fonctionne en temps O(n + m), où n et m sont les tailles des tableaux, et utilise de la mémoire supplémentaire pour le nouveau tableau.