import java.util.*;

class QuickSort6
// Destructive quick sort on a random array of integers
// (using temporary arrays).
// 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)
 {
  if(a.length>1)
     {
      Integer pivot = a[0];
      int count=0;
      for(int i=0; i<a.length; i++)
         if(a[i].compareTo(pivot)<0)
            count++;
      Integer[] smaller = new Integer[count];
      Integer[] greater = new Integer[a.length-count-1];
      for(int i=1, j=0, k=0; i<a.length; i++)
         if(a[i].compareTo(pivot)<0)
            smaller[j++]=a[i];
         else
            greater[k++]=a[i];
      sort(smaller);
      sort(greater);
      for(int i=0; i<count; i++)
         a[i]=smaller[i];
      a[count]=pivot;
      for(int i=0; i<greater.length; i++)
         a[count+i+1]=greater[i];
     }
 }

}