import java.util.*;

class QuickSort10
// Destructive quick sort on a random ArrayList 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();
  ArrayList<Integer> a = new ArrayList<Integer>();
  for(int i=0; i<num; i++)
      a.add(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(ArrayList<Integer> a)
 {
  sort(a,0,a.size());
 }

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

 private static void swap(ArrayList<Integer> a,int pos1,int pos2)
 {
  Integer temp = a.get(pos1);
  a.set(pos1,a.get(pos2));
  a.set(pos2,temp);
 }

}