/* Auteur: Nicolas JANEY          */
/* nicolas.janey@univ-fcomte.fr   */
/* Fevrier 2005                   */

public class FusionTableauxTriesEnConsole {

  /* Fonction de fusion de deux tableaux d'entiers tries  */
  /* en un tableau d'entiers tries                        */
  /* t1,t2 : tableaux d'entiers tries                     */
  /* Resultat fonction : Tableau d'entiers trie           */

  public static int [] fusion(int [] t1,int [] t2) {
  /* Calcul des tailles des tableau t1 et t2              */
    int n1 = t1.length;
    int n2 = t2.length;
  /* Creation d'un tableau de taille suffisante           */
  /* pour contenir toutes les valeurs de t1 et t2 :       */
  /* (n1+n2) valeurs                                      */
    int [] t = new int[n1+n2];
  /* Définition et initialisation a 0 de deux variables   */
  /* compteur (i1 et i2) pour stocker le nombre           */
  /* de valeurs de t1 et le nombre de valeurs de t2       */
  /* qui ont deja ete placees dans t                      */
    int i1 = 0;
    int i2 = 0;
  /* Pour les n1+n2 valeurs a placer dans t               */
    for ( int i = 0 ; i < n1+n2 ; i++ ) {
  /* Si toutes les valeurs de t1 sont deja dans t,        */
  /* la valeur a placer dans t est la premiere valeur     */
  /* de t2 non encore placee dans t                       */
      if ( i1 == n1 ) {
        t[i] = t2[i2];
        i2++; }
        else
  /* Sinon, si toutes les valeurs de t2 sont deja dans t, */
  /* la valeur a placer dans t est la premiere valeur     */
  /* de t1 non encore placee dans t                       */
        if ( i2 == n2 ) {
          t[i] = t1[i1];
          i1++; }
          else
  /* Sinon, si la premiere valeur de t1 non placee dans t */
  /* est plus petite que la premiere valeur de t2         */
  /* non placee dans t, alors c'est la valeur de t1       */
  /* qui va dans t                                        */
          if ( t1[i1] < t2[i2] ) {
            t[i] = t1[i1];
            i1++; }
            else {
  /* Sinon, c'est la valeur de t1 qui va dans t           */
            t[i] = t2[i2];
            i2++; } }
  /* Resultat fonction : le tableau t ainsi cree          */
  /* et rempli                                            */
    return(t);
  }

  /* Fonction de creation d'un tableau trie d'entiers     */
  /* tires au hasard                                      */
  /* taille : nombre d'entiers du tableau                 */

  public static int [] tableauTrie(int taille) {
  /* Creation d'un tableau de taille entiers              */
    int [] t = new int[taille];
  /* Initialisation de t[0] avec un entier tire au sort   */
  /* dans l'intervalle [0,4]                              */
    t[0] =(int) (Math.random()*5);
  /* Pour toutes les valeurs restant a initialiser        */
    for ( int i = 1 ; i < t.length ; i++ )
  /* La valeur d'indice i est affectee avec la valeur     */
  /* d'indice i-1 a laquelle on ajoute une valeur         */
  /* tiree au sort dans l'intervalle [0,4]                */
      t[i] = t[i-1] + (int) (Math.random()*5);
  /* Resultat fonction : le tableau t ainsi initialise    */
    return(t);
  }

  /* Fonction d'affichage d'un tableau d'entiers          */
  /* t : tableau dont les valeurs doivent etre affichees  */

  public static void afficheTableau(int [] t) {
    int i;
    for ( i = 0 ; i < t.length ; i++ )
      Console.out.print(t[i]+" ");
    Console.out.println();
  }

  /* Fonction principale                                  */

  public static void main(String [] args) {
    Console.setTitle("FusionTableauxTries");
  /* Lecture au clavier des donnees initiales             */
    Console.out.print("Taille du premier tableau : ");
    int n1 = Integer.valueOf(Console.in.readLine()).intValue();
    Console.out.print("Taille du second tableau  : ");
    int n2 = Integer.valueOf(Console.in.readLine()).intValue();
  /* Generation des tableaux a fusionner                  */
    int [] t1 = tableauTrie(n1);
    int [] t2 = tableauTrie(n2);
  /* Affichage des tableaux a fusionner                   */
    Console.out.println("Premier tableau :");
    afficheTableau(t1);
    Console.out.println("second tableau  :");
    afficheTableau(t2);
  /* Fusion des tableaux                                  */
    int [] t = fusion(t1,t2);
  /* Affichage du tableau issu de la fusion               */
    Console.out.println("Tableau fusionne :");
    afficheTableau(t);
  }
}