/** Contains static methods for sorting, together with the methods 
    that they use. */
public class Sorting  {
   
   /** Given h < k, return the position of the minimum value of b[h..k] */
   public static int min(int[] b, int h, int k) {
      int p= h; // will contain index of minimum
      int i= h;
      // {inv: b[p] is the minimum of b[h..i]}
      while (i!= k) {
         i= i+1;
         if (b[i] < b[p])
            {p= i;}
      }
      return p;
   }
   
   /** b[h..k-1] is sorted, and b[k] contains a value
       Sort b[h..k]  */
   public static void insertValue(int[] b, int h, int k) {
      // This algorithm works as follows.
      // 1. b[k] is placed in v.
      // 2. All elements b[k-1], b[p-2], ... that are >= v
      //    are moved up to b[k], b[k-1], ... 
      // 3. v is placed in the vacated position.
      int v= b[k];
      int i= k;
      /* inv P: (1) Placing v in b[i] makes b[h..k] a
                    permutation of its initial value
                (2) b[h..k] with b[i] removed is initial b[h..k-1]
                (3) v < b[i+1..k]
                */
      while ((i != h) && v < b[i-1]) {
         b[i]= b[i-1];
         i= i-1;
      }
      b[i]= v;
   }
   
   /** = index of x in b ---or b.length if x is not in */
   public static int linearSearch(int[] b, int x) {
      // invariant: x is not in b[0..i-1]
      int i;
      for (i= 0; i != b.length && b[i] != x; i++)
          {}
      return b.length;
   }
   
   /** Precondition: b is in ascending order. Return a values
       i that satisfies R: b[i] <= x < b[i+1] */
   public static int binarySearch(int[] b, int x) {
      int i= -1; int j= b.length;
      // {P:b[i] <= x < b[j] and -1 <= i < j <= b.length}
      while (j != i+1) {
         int e= (i+j)/2;
         // {-1 <= i < e < j <= b.length}
         if (b[e] <= x) i= e;
         else j= e;
      }
      return i;
   }
   
   /** Sort b --put its elements in ascending order */
   public static void selectionSort(int[] b) {
      int j= 0;
      // {inv P: b[0..j-1] is sorted and b[0..j-1] <= b[j..]}
      while (j != b.length) {
         int p= min(b, j, b.length-1);
         // {b[p] is minimum of b[j..b.length-1]}
         // Swap b[j] and b[p]
            int t= b[j]; b[j]= b[p]; b[p]= t;
         j= j+1;
      }
   }
   
   /** Sort b --put its elements in ascending order */
   public static void selectionSort1(int[] b) {
      int j= 0;
      // {inv P: b[0..j-1] is sorted and b[0..j-1] <= b[j..]}
      while (j != b.length) {
         // Put into p the index of smallest element of b[j..]
            int p= j; 
            for (int i= j+1; i != b.length; i++) {
               if (b[i] < b[p])  p= i;
            }
         // Swap b[j] and b[p]
            int t= b[j]; b[j]= b[p]; b[p]= t;
         j= j+1;
      }
   }
   
   /** Sort b[h..k] --put its elements in ascending order */
   public static void insertionSort(int[] b, int h, int k) {
      // inv: h < j <= k+1  and  b[h..j-1] is sorted
      for (int j= h+1; j <= k; j++) {
         // Sort b[h..j], given that b[h..j-1] is sorted
            insertValue(b,h,j);
      } 
   }
   
    /** Sort b[h..k] */
   public static void quicksort(int[] b, int h, int k) {
      tailRecursionLoop: while(true) {         
         if (k+1-h < 10) {
            insertionSort(b,h,k);
            return;
         }
         medianOf3(b,h,k);
         // {b[h] is between b[(h+k)/2] and b[k]}
         int j= partition(b,h,k);
         // b[h..j-1] <= b[j] <= b[j+1..k]
         if (j-h <= k-j) {
            quicksort(b,h,j-1);
            // quicksort(b,j+1,k);
               h= j+1;
               continue tailRecursionLoop;
         }
         else {
            quicksort(b,j+1,k);
            // quicksort(b,h,j-1);
               k= j-1;
               continue tailRecursionLoop;
         }
      } // tailRecursionLoop
   }
   
    /** b[h..k] has at least three elements. Let x be 
      the value initially in b[h]. Permute b[h..k]
      and return integer j satisfying R:<br><br>
    
         b[h..j-1] <= b[j] = x <= b[j+1..k]
      */
   public static int partition(int[] b, int h, int k) {
      // {Q: Let x be the value initially in b[h]}
      int j;
      // Truthify R1: b[h+1..j] <= b[h] = x <= b[j+1..k];
         int i= h+1; j= k;
         // {inv P: b[h+1..i-1] <= b[h] = x <= b[j+1..k]}
         while (i <= j) {
            if (b[i] < b[h]) i= i+1;
            else if (b[j] > b[h]) j= j-1;
            else {// {b[j] < x < b[i]}
               int t1= b[i]; b[i]= b[j]; b[j]= t1;
               i= i+1; j= j-1;
            }
          }
      int t= b[h]; b[h]= b[j]; b[j]= t;
      // {R}
      return j;
   }
   
   /** Permute b[h], b[(h+k)/2], and b[k] to put their median in b[h] */
   public static void medianOf3(int[] b, int h, int k) {
      int e= (h+k)/2;  // index of middle element of array
      int m;           // index of median
      // Return if b[h] is median; else store index of median in m
         if (b[h] <= b[e]) {
            if (b[h] >= b[k]) return;
            // {b[h] is smallest of the three}
            if (b[e] <= b[k]) m= e;
            else m= k;
         }
         else {
            if (b[h] <= b[k]) return;
            // {b[h] is largest of the three}
            if (b[e] <= b[k]) m= k;
            else m= e;
         }
      int t= b[h]; b[h]= b[m]; b[m]= t;
   }
   
}