public class PreMergeSort
{
    public static void main(String[] args)
    {
        double[] myList = {5, 8, 2, 4, 7, 3};
        
        for (int i = 0; i < myList.length; i++)
            System.out.print( myList[i] + "  ");
        System.out.println();
        
        mergeSort( myList );
        
        for (int i = 0; i < myList.length; i++)
            System.out.print( myList[i] + "  ");
        System.out.println();
    }

    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 - you can any sort algorithm !
        insertionSort( left );
        insertionSort( 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++];
        }
    }
    
    public static void insertionSort(double[] list) 
    {
        for (int i = 1 ; i < list.length; i++) 
        {
            double currentElement = list[i];  // Remove list[i] and                                            // save in currentElement

            // Find the correct position for currentElement
            int k;
            for (k = i - 1; k >= 0; k--) 
                if ( list[k] > currentElement )
                   list[k + 1] = list[k]; // Move list[k] up one spot
                else
                   break;                 // Found the insert position

            // Insert currentElement after list[k]
            list[k + 1] = currentElement;
        }
    } 
}