Merging two arrays without using extra space

Question

I have 2 sorted arrays, a1 and a2, of lengths l1 and l2, respectively. The array a2 has empty space at the end of length l1, so it can hold all of the elements of a1 in addition to its own elements. Now, I want to merge a1 into a2 so that a2 will contain all the elements of a1 and a2 in sorted order. Ideally this should use O(1) auxiliary storage space. I have the following cod,e but something is going wrong:

 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< l1;i++){

             if(j<fs){
                // System.out.println("i= " + i + "a1[i]=" + a1[i]);
                // System.out.println("j= " + j + "a2[j]=" + a2[j]);
                 if(a1[i]<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>p;i--){
              a[i]= a[i-1];
        }
        a[p]= key;
    }

Does anyone have any ideas on how to fix this? I used following data to run the code:

int a1[]= new int[]{-1,0,7,8};
int a2[]= new int[7];
a2[0]=1;
a2[1]=3;
a2[2]=9;

Output is

l1 =4 l2=7
es= 3
fs = 4
-1
0
1
3
9
0
0

Answer 1

It's difficult to tell what your code does, but it seems to have suboptimal (O(n^2)) complexity: there's a second loop inside add method.
Also, note that fs is always equal to l1.

But there's much simpler method: from the back. If you think about it, there's always enough space.

Something like this

int i = l1 - 1;
int j = l2 - 1;
int result_pos = l1 + l2 - 1;
while (i >= 0 || j >= 0) {
    if (a1[i] >= a2[j]) {
        a2[result_pos--] = a1[i--];
    } else {
        a2[result_pos--] = a2[j--];
    }
}

PS You'll need to add handling for the case when one of i and j is negative in the loop. Obviously, in this case another element should be copied.

edit
Later can be done with this condition

if (j < 0 || (i >= 0 && a1[i] >= a2[j])) {

instead of

if (a1[i] >= a2[j]) {