Comment fusionner deux tableaux triés en un seul, en conservant l'ordre des éléments?

Pour fusionner deux tableaux triés en un seul trié, on peut utiliser un algorithme de fusion similaire à celui utilisé dans le tri par fusion (merge sort). L'idée est de parcourir simultanément les deux tableaux, en comparant les éléments actuels, et d'ajouter le plus petit d'entre eux au tableau résultant.

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
}

Cette méthode fonctionne en temps O(n + m), où n et m sont les tailles des tableaux d'origine.