import java.util.*;

class InsertSort7
// Destructive insertion sort of a random array of integers
// Timed but not printed
{
 public static void main(String[] args) throws Exception
 {
  Random rand = new Random();
  long time1,time2;
  Scanner input = new Scanner(System.in);
  System.out.print("Enter the number of numbers: ");
  int num = input.nextInt();
  System.out.print("Enter the highest number: ");
  int high = input.nextInt();
  Integer[] a = new Integer[num];
  for(int i=0; i<num; i++)
      a[i]=rand.nextInt(high);
  time1 = new Date().getTime();
  sort(a);
  time2 = new Date().getTime();
  System.out.println("Time taken to sort: "+(time2-time1)+"ms");
 }

 public static void sort(Integer[] a)
 {
  for(int i=1; i<a.length; i++)
     insert(a[i],a,i);
 }

 private static void insert(Integer n,Integer[] a,int i)
 {
  for(; i>0&&a[i-1].compareTo(n)>0; i--)
     a[i]=a[i-1];
  a[i]=n;
 }


}