Comment réaliser la fusion de deux tableaux triés en un seul tableau trié?

Pour fusionner deux tableaux triés en un seul tableau trié, on peut utiliser un algorithme de fusion similaire à celui utilisé dans le tri par fusion (merge sort).

Idée :

• Parcourir les deux tableaux avec deux indices.
• À chaque étape, comparer les éléments actuels et ajouter le plus petit au tableau résultant.
• Lorsqu’un des tableaux est terminé, ajouter les éléments restants de l’autre tableau.

Exemple en Go :

func mergeSortedArrays(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0

    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }

    // Ajouter les éléments restants
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)

    return result
}

Cet algorithme fonctionne en temps O(n + m), où n et m sont les tailles des tableaux d’entrée.