public class ArraySort
{
  // This class contains static methods for sorting arrays
  // The arrays passed to be sorted must contain mutually
  // comparable objects

  private static final int threshold = 35;

  public static void quicksort(Comparable[] array)
  {
    quicksortHelper(array, 0, array.length - 1);
  }

  private static void quicksortHelper(Comparable[] array, int first, int last)
  {
    // to be completed
  }

  private static int partition(Comparable[] array, int first, int last)
  {
    int pivotPos = medianOfThreeIndex(array, first, last);
    Comparable pivotValue = array[pivotPos];
    array[pivotPos] = array[last];
    array[last] = pivotValue;

    int low = first;
    int high = last-1;

    while(low <= high)
    {
      while(array[low].compareTo(pivotValue) < 0)
        low++;

      while(high >= low && array[high].compareTo(pivotValue) >= 0)
        high--;

      if(low < high)
      {
        Comparable temp = array[low];
        array[low] = array[high];
        array[high] = temp;
      }
    }
    Comparable temp = array[low];
    array[low] = array[last];
    array[last] = temp;

    return low;
  }

  private static int medianOfThreeIndex(Comparable[] array, int first, int last)
  {
    int mid = (first + last) / 2;

    if((array[first].compareTo(array[mid]) <= 0 && array[mid].compareTo(array[last]) <= 0) ||
       (array[first].compareTo(array[mid]) >= 0 && array[mid].compareTo(array[last]) >= 0))
      return mid;
    else if((array[first].compareTo(array[last]) <= 0 && array[last].compareTo(array[mid]) <= 0) ||
            (array[first].compareTo(array[last]) >= 0 && array[last].compareTo(array[mid]) >= 0))
      return last;
    else // ((array[mid].compareTo(array[first]) <= 0 && array[first].compareTo(array[last]) <= 0) ||
         //  (array[mid].compareTo(array[first]) >= 0 && array[first].compareTo(array[last]) >= 0))
      return first;
  }

  public static void insertSort(Comparable[] array)
  {
    insertSortHelper(array, 0, array.length-1);
  }

  private static void insertSortHelper(Comparable[] array, int first, int last)
  {
    // to be completed
  }

  public static void quicksort2(Comparable[] array)
  {
    // to be completed
  }


}