Merge Two Sorted Arrays.

Problem : There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

Solution: The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.

Code:

public class MergeSortedArrays {

   public static void main(String[] args) {

       int[] a = new int[] {3,6,10,12,56};

       int[] b = new int[8] ;

       b[0] = 9;

       b[1] =11;

       b[2] =36;

       //after this b looks like {9,11,36,0,0,0,0,0}

       // with enough space to accommodate 'a'

       //0 indicating a free space.

       int i = a.length-1; //a's length

       int k = b.length-1; //b's length

       //Starting point to the empty slots.

       int j = findCount(b) - 1;

       for(; k>0; k--) {

           if(j<0)

               break;



           if(a[i] > b[j])

           {

               b[k] = a[i];

               i--;

           }

           else

           {

               b[k] = b[j];

               j--;

           }

           print(b);

       }

       //Copy the leftovers which are already sorted.

       while(k>=0){

               b[k--] = a[i--];



       }

      print(b); //Final array is printed.

   }

   //Purely a debug method

   private static void print(int[] b){

       for(int x=0;x           System.out.print(b[x] + ", ");



       System.out.println("");

   }

   private static int findCount(int[] b)

   {   int i=0;

       while (b[i] != 0){

          i++;

       }

       return i;

   }

}