public static void insertionSort(double[] list) 
    {
        for (int i = 1 ; i < list.length; i++) 
        {
            /** insert list[i] into a sorted sublist list[0..i-1] 
	        so that:  list[0..i] is sorted. */

            double currentElement = list[i];  // Remove list[i] and 
                                              // save in currentElement

            // Look for element list[k] that preceeds (≤) 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;
        }
    } 

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

	Random r = new Random(1); // Generate the SAME ramdom numbers

        for (int i = 0; i < myList.length; i++)
            myList[i] = 100*r.nextDouble();

	Date startTime = new Date();  // Record the current time before running

        insertionSort(myList);        // Execute

	Date endTime = new Date();    // Record the current time after running

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

    public static void mergeSort(double[] a)  // 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 - the mergeSort algorithm is recursive !
	mergeSort( left );      // We use mergeSort itself here !
	mergeSort( right );     // We use mergeSort again here !

	// Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    } 

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

	Random r = new Random(1); // Generate the SAME ramdom numbers

        for (int i = 0; i < myList.length; i++)
            myList[i] = 100*r.nextDouble();

	Date startTime = new Date();  // Record the current time before running

        mergeSort(myList);        // Execute

	Date endTime = new Date();    // Record the current time after running

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