import java.util.Date;

public class MergeSort
{
    public static void main(String[] args)
    {
        final int N = 200000; // Use 100000 and 200000
        double[] myList = new double[N];

        for (int i = 0; i < myList.length; i++)
            myList[i] = Math.random();

        Date startTime = new Date();  // Record the start time

        mergeSort(myList);            // Execute
  
        Date endTime = new Date();    // Record the end time

        System.out.println("Elasped time = " + 
                 (endTime.getTime() - startTime.getTime()) + " msec");
    }

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
        int middle     = a.length/2;
        double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
        if ( a.length == 1 )   // Base case
            return;            // No need to sort an array of 1 element...

        // Split:       a[0 ..... middle-1]  a[middle .... a.length-1]      
        //    as:     left[0 .. middle-1]  right[0 ... a.length-1-middle] 
        for ( int i = 0; i < middle; i++ )
           left[i] = a[i];

        for ( int i = 0; i < a.length-middle; i++ )
           right[i] = a[i+middle];

        // Sort both halves - mergeSort is recursive
        mergeSort( left );
        mergeSort( right );

        // Merge both sorted arrays 
        merge( a, left, right );   // We have discussed merge() already...   
    } 
    
    
    // merge(result, a, b): merge 2 sorted arrays a and b into array result
    public static void merge(double[] result, double[] a, double[] b)      
    {
        int i = 0, j = 0, k = 0;  // Indexes for arrays: a[i], b[j], result[k]

        while ( i < a.length || j < b.length )
        {
            if ( i < a.length && j < b.length )
            {  // Both arrays have unprocessed elements
                if ( a[i] < b[j] )
                    result[k++] = a[i++];
                else
                    result[k++] = b[j++];
            }
            else if ( i == a.length )     // a is exhausted (empty)
                result[k++] = b[j++];
            else if ( j == b.length )     // b is exhausted (empty)
                result[k++] = a[i++];
        }
    }
}