Algorithmique et Structures de Données

Solution :

Algorithme (Fusion de tableaux triée) :
Entrée : Tableaux T1, T2 triés de taille t1, t2,
               Tableau T alloué de taille t = t1 + t2
Sortie : T avec les contenus T1 et T2 trié

Début
    i1 <- 0; i2 <- 0; i <- 0
   tant que i1 < t1 et i2 < t2 faire
      si T1[i1] < T2[i2] alors
          T[i] <- T1[i1]; i++; i1++
      sinon
          T[i] <- T2[i2]; i++; i2++

      finsi

   fintantque
   si i1 < t1 alors
       tant que i1 < t1 faire
            T[i] <- T1[i1]; i++; i1++

       fintantque
   sinon
        tant que i2 < t2 faire
             T[i] <- T2[i2]; i++; i2++

        fintantque

    finsi

Fin.

=> Complexité : Θ(N) (N=t)