import java.util.*;

class QuickSort8
// Destructive quick 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)
 {
  sort(a,0,a.length);
 }

 private static void sort(Integer[] a,int from,int to)
 {
  if(to>from+1)
     {
      Integer pivot = a[from];
      int low=from+1,high=to-1;
      while(low<high)
         {
          while(low<high&&a[low].compareTo(pivot)<0)
              low++;
          while(pivot.compareTo(a[high])<0)
              high--;
          if(low<high)
            { 
             swap(a,high,low);
             low++;
             high--;
            }
         }
      while(pivot.compareTo(a[high])<0)
         high--;
      swap(a,from,high);
      sort(a,from,high);
      sort(a,high+1,to);
     }
 }

 private static void swap(Integer[] a,int pos1,int pos2)
 {
  Integer temp = a[pos1];
  a[pos1]=a[pos2];
  a[pos2]=temp;
 }

}