import java.util.Date;

public class InsertionSort
{
    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

        insertionSort(myList);        // Execute

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

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

    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;
        }
    } 
}