import myIO.*;

public class Sorts  {

  private static boolean trace;  // set true for trace

  public static void setTrace(boolean b) {
    trace = b;
  }

public static void insertionSort(int a[], int first, int last) {
    // insert each element, starting with the 2nd
    for (int pNext = first + 1; pNext <= last; pNext++) {
        // invariant: a[0] .. a[pNext - 1] is sorted.
        int next = a[pNext];

        // starting with last element in sorted subarray (subscript pNext - 1),
        //     shift all elements > next one position to the right
        int j = pNext;
        while (j > first && a[j-1] > next) {
            // invariant: j >= 0 and all prior elements checked > next
            a[j] = a[j-1];  // shift right
            j--;            // check next element
        }

        // assert: j is 0 or a[j-1] <= next, so next belongs at position j
        a[j] = next;
    }
}

public static void insertionSort(int a[]) {
   insertionSort(a, 0, a.length-1);
}

public static void selectionSort(int[] a) {
    int posMin, temp;

    for (int i = 0; i < a.length - 1; i++) {

       // Select smallest in a[i]..a[a.length]
       posMin = i;  // assume a[i] is smallest
       for (int j = i + 1; j < a.length; j++)
          if (a[j] < a[posMin]) posMin = j;

       // Exchange a[i], a[posMin]
       temp = a[i];   a[i] = a[posMin];   a[posMin] = temp;
    }
}


  public static void bubbleSort(int[] a) {
     boolean done = false;  // Go through sort body at least one time
     int last = a.length;   // last element to examine in each pass
     int temp;

     while (!done) {
        done = true;   // Are we done yet?.
        for (int i = 0; i < last - 1; i++)
           if (a[i] > a[i+1]) {    // switch them
              temp = a[i];
              a[i] = a[i+1];
              a[i+1] = temp;
              done = false;     // No, we're not done
           }
        last--;   // elements from last to right are sorted
    }
  }



public static void shellSort(int [] a) {
    for (int gap = a.length / 2; gap > 0; gap = (int) (gap / 2.2)) {
        if (gap == 2) gap = 1;
        //System.out.println(gap);
        for (int pNext = gap; pNext < a.length; pNext++) {
            int next = a[pNext];

            int j = pNext;
            while (j >= gap && a[j-gap] > next) {
                 a[j] = a[j-gap];  // shift right
                 j-=gap;            // check next element
             }
             a[j] = next;
         }
    }
}



private static void mergeSort(int[] x, int [] temp, int first, int last) {
   //System.out.println(first + "  " + last);
   if (first < last) {  // array has 2 or more elements
      int mid = (first + last) / 2;
      mergeSort(x, temp, first, mid);   // sort left half of x
      mergeSort(x, temp, mid+1, last);   // sort right half of x
      merge (x, temp, first, mid+1, last);  // merge 2 halves - pass arrays x, temp,
            // subscript of leftmost element in each half and subscript of last element
   }
}

public static void mergeSort(int[] x) {
   int[] temp = new int[x.length];   // temporary array
   mergeSort(x, temp, 0, x.length-1);
}

 private static void merge(int[] x, int[] temp, 
                          int leftPos, int rightPos, int rightEnd) {
    int leftEnd = rightPos - 1;
    int tempPos = leftPos;
    int numEl = rightEnd - leftPos + 1;

    // main merge loop - exit after last element in either subarray is copied
    // Start by comparing elements at leftPos and rightPos
    // while the end of either array is not reached
    while (leftPos <= leftEnd && rightPos <= rightEnd) {
         if (x[leftPos] < x[rightPos]) { // copy element at leftPos and advance
              temp[tempPos] = x[leftPos];   tempPos++;   leftPos++;

         } else {        // copy element at rightPos and advance
              temp[tempPos] = x[rightPos];   tempPos++;   rightPos++;
         }
    }
        // merge any elements remaining - only one subarray can have any
        while (leftPos <= leftEnd)
              temp[tempPos++] = x[leftPos++];  // increment after copy


        while (rightPos <= rightEnd)
              temp[tempPos++] = x[rightPos++];
         // copy elements of array temp into corresponding positions of array x
         for (int i = 0; i < numEl; i++ ) // start at right end of array temp
          {    x[rightEnd] = temp[rightEnd];
               //System.out.println(rightEnd);
               rightEnd--;
          }
 }

private static void quickSort(int[] x, int first, int last) {
   int cutOff = 2;
   if ((last - first) < cutOff)
     insertionSort(x, first, last);
   else   {  // array has more than cutOff elements
      // partiton the array, saving the pivot index

      // sort left partition using quicksort

      // sort right partition using quicksort

   }
}

public static void quickSort(int[] x) {
   quickSort(x, 0, x.length-1);

}

public static int findMiddle(int[] x, int first, int last) {
   int mid = (first + last) / 2;
   if (x[mid] >= x[first] && x[mid] <= x[last] ||
       x[mid] >= x[last] && x[mid] <= x[first])
       return mid;
   else if (x[first] >= x[mid] && x[first] <= x[last] ||
            x[first] >= x[last] && x[first] <= x[mid])
       return first;
   else
       return last;
}

public static int partition(int[] x, int first, int last) {
   // partitions the array and returns pivot index - new position
   //   of pivot value.

}

private static void exchange(int[] x, int a, int b) {
   int temp = x[a];  x[a] = x[b];  x[b] = temp;
}

}