import java.util.*;

class QuickSort11
// Destructive quick sort of a random array of integers
// Done using a stack of from/to pairs rather than recursion
{
 public static void main(String[] args) throws Exception
 {
  Random rand = new Random();
  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);
  System.out.println("The numbers are stored in an array as:");
  System.out.println(Arrays.toString(a));
  sort(a);
  System.out.println("After sorting the array is:");
  System.out.println(Arrays.toString(a));
 }

 public static void sort(Integer[] a)
 {
  ArrayList<Pair> stack = new ArrayList<Pair>();
  stack.add(new Pair(0,a.length));
  while(stack.size()>0)
     {
      Pair p=stack.remove(stack.size()-1);
      int from=p.from;
      int to=p.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);
          stack.add(new Pair(from,high));
          stack.add(new Pair(high+1,to));
         }
     }
 }

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

 private static class Pair
 {
  int from, to;
  
  Pair(int f,int t)
  {
   from=f;
   to=t;
  }
 }

}