Monday, September 2, 2013

Merge Two Sorted Arrays

Merge Two Sorted Arrays into one of the Arrays

Given two sorted arrays, denoted as array1 and array2, 
Merge them into array1 and keep the merged array sorted.
** Assumption: Array1 has enough space to accomodate the elements of Array2
Java Program to Merge Two sorted arrays

public class MergeSortedArrays {
/**
 *                                                                                           |
 *                                                                                           index1
 * .................n..........n.............n.........n.............n.......................n............n...n............        ---> Number line for Array1, has 8 numbers in ascend
 * .....n...n...........n........ n...n..........n.........n....................................................................       ----> Number line for Array2
 *                                              index2
 *                                               |
 * In the above number line 'n' stands for a number in the number line for natural numbers for the given array
 *
 *
 */
   
    public int[] merge( int[] array1, int[] array2, int length1, int length2 ) {
        if ( array1 == null )
            throw new IllegalArgumentException("Invalid array to merge" );
       
        if ( array2 == null || array2.length == 0 )
            return array1;
       
        int index1 = length1- 1;
        int  index2 = length2 -1;
        int mergedBoundary = length1 + length2 - 1;
   
        while( index1 >= 0 && index2 >= 0) {
            if ( array1[index1] > array2[index2] ) {
                array1[mergedBoundary--] = array1[index1--];
            }else {
                array1[mergedBoundary--] = array2[ index2-- ];
            }
        }
        while ( index2 >= 0 ) {
            array1[ mergedBoundary--] = array2[index2--];
        }
       
        return array1;   
       
    }
   
    public static void print( int[] ar, int len ) {
        int i = 0;
        while ( len-- > 0)
            System.out.println( ar[i++ ]);
    }
   
    public static void main( String[] args ) {
        /*
      * .................n..........n.............n.........n.............n.......................n............n..........        ---> Number line for Array1, has 8 numbers in ascend
     * .....n...n...........n......... n...n..........n.........n.................................................................... 
         * */
   
        int[] ar1 = new int[] { 45, 56, 77, 89, 150, 187, 198, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int len1 = 7;
       
        int[] ar2 = new int[] { 23, 29, 47, 59, 67, 80, 106 };
        int len2 = 7;
        MergeSortedArrays merge = new MergeSortedArrays();
        int[] ar3 = merge.merge( ar1, ar2,  len1, len2 );
        print( ar3, len1+len2 );
    }
}


No comments:

Post a Comment