title: Merging two arrays without using extra space
body: <p>I have 2 sorted arrays, <code>a1</code> and <code>a2</code>, of lengths <code>l1</code> and <code>l2</code>, respectively.  The array <code>a2</code> has empty space at the end of length <code>l1</code>, so it can hold all of the elements of <code>a1</code> in addition to its own elements.  Now, I want to merge <code>a1</code> into <code>a2</code> so that <code>a2</code> will contain all the elements of <code>a1</code> and <code>a2</code> in sorted order.  Ideally this should use O(1) auxiliary storage space.  I have the following cod,e but something is going wrong:</p>
  
  <pre><code> public static int[] merge(int []a1,int a2[],int l1, int l2){
  
           System.out.println("l1 =" +l1 + " l2=" +l2);
           int es = l2-l1;
           int fs = l2-es;
  
           System.out.println("es= " +es);
           System.out.println("fs = " + fs);
           int j=0;
  
           for(int i=0;i&lt; l1;i++){
  
               if(j&lt;fs){
                  // System.out.println("i= " + i + "a1[i]=" + a1[i]);
                  // System.out.println("j= " + j + "a2[j]=" + a2[j]);
                   if(a1[i]&lt;a2[j]){
                       add(a2,j,a1[i],l2);
                       //i++;
                       fs++;
                   }
               }else{
                   System.out.println("***");
                   a2[j]=a1[i];
               }
  
               j++;
           }
  
           return a2;
       }
  
  
      public static void add(int []a,int p,int key,int l){
  
          for(int i=l-1;i&gt;p;i--){
                a[i]= a[i-1];
          }
          a[p]= key;
      }
  </code></pre>
  
  <p>Does anyone have any ideas on how to fix this?  I used following data to run the code:</p>
  
  <pre><code>int a1[]= new int[]{-1,0,7,8};
  int a2[]= new int[7];
  a2[0]=1;
  a2[1]=3;
  a2[2]=9;
  </code></pre>
  
  <p>Output is</p>
  
  <pre><code>l1 =4 l2=7
  es= 3
  fs = 4
  -1
  0
  1
  3
  9
  0
  0
  </code></pre>