/**
 * Matt Kretchmar
 * February 24, 2006
 * ArrayMerge.java
 * This program merges two arrays of numbers into a new, single larger
 * array.  The two starting arrays have numbers in sorted order and we
 * desire the large array to also have all the same numbers (combined)
 * in sorted order from smallest to biggest.  We will select numbers,
 * one at a time, from the two smaller arrays.  The next number we select
 * will be the smaller of the two next numbers from each array.  We will
 * continue in this way until one of the smaller arrays is empty.  Then
 * we will put the remaining numbers from the other array into the big
 * array.
 */

import java.util.Random;

class ArrayMerge
{
    public static void main ( String []args )
    {
        final int SIZE1 = 5;
        final int SIZE2 = 7;
        final int SIZE3 = SIZE1+SIZE2;
        int []smallArray1 = new int[SIZE1];
        int []smallArray2 = new int[SIZE2];
        int []bigArray = new int[SIZE3];

        Random generator = new Random();

        int i = 0;  // traces indices in small array 1
        int j = 0;  // traces indices in small array 2
        int k = 0;  // traces indices in large array
        
        // Use random numbers to fill in small arrays.  If we want
        // the arrays to be in sorted order, we can add small amounts
        // to the previous number in the array to get the next one.
        // That way each new number will be at least as big as the
        // previous ones. 
        for ( i = 0; i < SIZE1; i++ )
        {
            smallArray1[i] = smallArray1[i-1] + generator.nextInt(4);
        }

        for ( j = 0; j < SIZE1; j++ )
        {
            smallArray2[j] = smallArray2[j-1] + generator.nextInt(4);
        }
        
        
        // repeat while we are not yet at the end of either small array
        while ( i < SIZE1 && j < SIZE2 )
        {
            if ( smallArray1[i] < smallArray2[j] )
            {
                bigArray[k] = smallArray2[j];
                j++;
                k++;
            }
            else
                bigArray[k] = smallArray1[i];
                i++;
                k++;
        }
        
        // Now we are either done with the smallArray1 or smallArray2
        if ( i == SIZE1 )
        {
            // more in smallArray2
            while ( j < SIZE2 )
            {
                bigArray[k] = smallArray2[j];
                k++;
                j++;
            }
        }
        else
        {
            // more in smallArray1
            while ( i < SIZE1 )
            {
                bigArray[k] = smallArray1[i];
                k++;
                i++;
            }
        }
            
        // print the three arrays.
        System.out.print("smallArray 1: ");
        for ( i = 0; i < smallArray1.length; i++ )
        {
            System.out.print(smallArray1[i] + " ");
        }
        System.out.println();

        System.out.print("smallArray 2: ");
        for ( j = 0; j < smallArray2.length; j++ )
        {
            System.out.print(smallArray2[j] + " ");
        }
        System.out.println();

        System.out.print("bigArray : ");
        for ( k = 0; k < bigArray.length; k++ )
        {
            System.out.print(bigArray[k] + " ");
        }
        System.out.println();
            
    }
}