import java.io.*;
import java.util.*;   //for working with Vectorsclass MergSort
{
         String str;
         intvalue=0;
         staticint s1=0,s2=0;
         Vector list1 = new Vector();
         Vector list2 = new Vector();
         Integer intval; //object of Integer class for converting primitive numbers to object numbersvoid getdata()
     {
         try{
              System.out.println("\n=====MERGE SORT=====");
              BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
              System.out.println("\nNOTE :  Data should be entered in sorted order");
              System.out.print("\nEnter size of First List : ");
              System.out.flush();
              str=obj.readLine();
              s1=Integer.parseInt(str);
                 for(int i=0;i<s1;i++)        
                    {
                      System.out.print("Enter value for Element "+(i+1)+" :  ");
                      System.out.flush();
                      str=obj.readLine();
                      value=Integer.parseInt(str);
                      intval = new Integer(value);
                      list1.addElement(intval);
                  }

                System.out.print("\nEnter size of Second List : ");
              System.out.flush();
              str=obj.readLine();
              s2=Integer.parseInt(str);
                  for(    int i=0;i<s2;i++)
                   {
                      System.out.print("Enter value for Element "+(i+1)+" :  ");
                      System.out.flush();
                      str=obj.readLine();
                      value=Integer.parseInt(str);
                      intval=new Integer(value);
                      list2.addElement(intval);
                   }
            }
            catch(Exception e) {}
      }

                   //MERGE LOGICvoid merging()  //method to merg
                    {
                         for(int i=0;i<s2;i++)
                         {
                             list1.insertElementAt(list2.elementAt(i),(s1+i));
                        }
                        System.out.println("\n\nAFTER MERGING");
                        for(int i=0;i<s1+s2;i++)
                        {
                            System.out.println("Element at("+(i+1)+") : "+list1.elementAt(i));
                        }
                   }
                              
                //SORT LOGICvoid sorting() //method for sorting 
                {
                    //creating temporary arrayint size=list1.size();
                    Vector sort=new Vector();
                    int a,b; //extra for converting object to primitive numbers
                    Integer A,B; //extra for taking object valueint first=0,second=s1,third=s1+s2,i,j,c=0;
                   i=first;
                   j=second;
                   while(i<second && j<third)
                   {
                          A=(Integer)list1.elementAt(i);  //Assigning object to object
                          B=(Integer)list1.elementAt(j);  //Assigning object to object

                          a=A.intValue();  //converting object to primitive number
                          b=B.intValue();  //converting object to primitive numberif(a < b)   //list1.elementAt(i)   <    list1.elementAt(j)
                            {
                               sort.insertElementAt(A,c);
                               i++;
                            }
                          else
                            {
                              sort.insertElementAt(B,c);
                              j++;
                            }
                         c++;
                    }

                    if(i<second)
                    {
                          while(i<second)
                          {
                              sort.insertElementAt(list1.elementAt(i),c);
                              i++;
                              c++;
                         }
                    }

                    if(j<third)
                    {
                        while(j<third)
                        {
                              sort.insertElementAt(list1.elementAt(j),c);
                               j++;
                               c++;
                        }
                    }

                    System.out.println("\n\nAFTER SORTING");
                    for(int k=0;k<sort.size();k++)
                          System.out.println("Element at("+(k+1)+") : "+sort.elementAt(k));
            }

}


class  MergSortData
{
    publicstaticvoid main(String[] args) 
    {
         MergSort obj=new MergSort();
         obj.getdata();
         obj.merging();
         obj.sorting();
    }
}