Data Structures, Algorithms, & Applications in Java
Chapter 2, Exercise 6

To estimate the average run time to sort n distinct numbers, we can begin with an array of distinct numbers (say 0, 1, 2, ..., n - 1) and permute these numbers prior to a sort. A random permutation may be obtained by randomly selecting the element that is to be in position a[i], i = n - 1, n - 2, ..., 1. The code below does this.

// randomly permute a
for (int i = n-1; i > 0; i--)
{
   // select an element from a[0] to a[i]
   int j = Math.abs(r.nextInt()) % (i + 1);

   // swap i and j
   MyMath.swap(a, i, j);
}

public class TimeInsertionSort6
{
   public static void main(String [] args)
   {
      int step = 10;
      Random r = new Random();

      System.out.println("The average times, in milliseconds, are");
      System.out.println("n \trepetitions \telapsed time \ttime/sort");
      for (int n = 0; n <= 1000; n += step)
      {
         // create element array
         Integer [] a = new Integer[n];

         // initialize data
         for (int i = 0; i < n; i++)
            a[i] = new Integer(i);

         long startTime = System.currentTimeMillis();
         long counter = 0;
         while (counter < 20 || System.currentTimeMillis( ) - startTime < 1000)
         {
            counter++;
            // randomly permute a
            for (int i = n-1; i > 0; i--)
            {
               // select an element from a[0] to a[i]
               int j = Math.abs(r.nextInt()) % (i + 1);

               // swap i and j
               MyMath.swap(a, i, j);
            }

            // sort the elements
            InsertionSort2.insertionSort(a);
         }

         long elapsedTime = System.currentTimeMillis() - startTime;
         System.out.println(n + "\t" + counter + "\t\t" +
            + elapsedTime + "\t\t" + ((float) elapsedTime)/counter);

         if (n == 100) step = 100;
      }
   }
}

___________________________________________________________
    n      repetitions      elapsed time       time/sort
___________________________________________________________
    0            11568              1040            0.09
   10             9962              1040            0.10
   20             8573              1040            0.12
   30             7202              1050            0.15
   40             5918              1040            0.18
   50             4834              1050            0.22
   60             3990              1040            0.26
   70             3306              1040            0.31
   80             2781              1050            0.38
   90             2356              1040            0.44
  100             2018              1040            0.52
  200              627              1050            1.67
  300              296              1040            3.51
  400              172              1040            6.05
  500              112              1050            9.38
  600               77              1040           13.51
  700               57              1050           18.42
  800               44              1040           23.64
  900               34              1040           30.59
 1000               28              1050           37.50
___________________________________________________________