Sorting methods in Java.

public class Sorts {
 
  /*SLECTIONSORT ALGORITHM*/
  //precondition:  supply instantiated array of size 
  // many elements
  public static <Type extends Comparable<? super Type>> 
  void selectionSort(Type[] arr, int size) {
    Type temp;
    int minIndex;
 
    for (int i = 0; i < size - 1; i++) {
      minIndex = i;
      for (int j = i + 1; j < size; j++) {
        if (arr[j].compareTo(arr[minIndex]) < 0) {
          minIndex = j;
        }
      }
      temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
    }
  }
  //postcondition:  returns parameter argument arr in 
  // ascending sorted order
 
 
  /*BUBBLESORT ALGORITHM*/
  //precondition:  supply instantiated array of size 
  // many elements
  public static <Type extends Comparable<? super Type>> 
  void bubbleSort(Type[] arr, int size) {
    boolean done = false;
    Type temp;
 
    while(!done) {
      done = true;
      for (int index = 0; index < size - 1; index ++) {
        if (arr[index].compareTo(arr[index + 1]) > 0) {
          temp = arr[index];
          arr[index] = arr[index + 1];
          arr[index + 1] = temp;
          done = false;
        }
      }
    }
  }
  //postcondition:  returns parameter argument arr in 
  // ascending sorted order
 
  /*INSERTIONSORT ALGORITHM*/
  //precondition:  supply instantiated array of size 
  // many elements
  public static <Type extends Comparable<? super Type>> 
  void insertionSort(Type[] arr, int size) {
    Type save;
    for (int i = 0; i < size; i++) {
      save = arr[i];
      int j = i;
      //move elements while they are greater than 
      // save value
      while (j > 0 && arr[j - 1].compareTo(save) > 0) {
        arr[j] = arr[j - 1];
        j--;
      }
      arr[j] = save;
    }
  }
  //postcondition:  returns parameter argument arr 
  // in ascending sorted order
 
 
  /*HEAPSORT ALGORITHM*/
  //precondition:  supply instantiated array of size 
  // many elements
  public static <Type extends Comparable<? super Type>> 
  void heapSort(Type[] arr, int size) {
    if (size > 0) {
      Type[] temp = (Type[])new Comparable[size];
      int tempLength = size;
 
      //step 1. buildHeap    
      for (int index = (size / 2) - 1; index >= 0; index--) {
        percolateDown(arr, size, index);
      }
      //step 2. sortList
      for (int index = 0; index <= size - 2; index++) {
        temp[index] = arr[0]; //save root to temp array
        arr[0] = arr[tempLength - 1]; //put last element into root
        tempLength--; //decrease array length
        percolateDown(arr, tempLength, 0); //percolate root node
      }
      temp[size - 1] = arr[0]; //handles last element
      //step 3. copyList
      System.arraycopy(temp, 0, arr, 0, size);
    }
  }
  //postcondition:  returns parameter argument arr in 
  // ascending sorted order
 
  //precondition:  supply instantiated array of size 
  // any elements and index of hole to be percolated down
  private static <Type extends Comparable<? super Type>> 
  void percolateDown(Type[] arr, int size, int x) {
    int hole = x;
    Type item = arr[x];
    int newHole = newHole(arr, size, hole, item);
    while(newHole != -1) {
      arr[hole] = arr[newHole];
      hole = newHole;
      newHole = newHole(arr, size, hole, item);
    }
    arr[hole] = item;
    return;
  }
  //postcondition:  percolates down an index to 
  // correct location to maintain heap quality
 
  //precondition:  supply instantiated array of 
  // size many elements, index of current hole, 
  // and item to be compared against possible new holes
  private static <Type extends Comparable<? super Type>> 
  int newHole(Type[] arr, int size, int hole, Type item) {
    int newHole = -1;
    //checks for children
    if (2*hole + 2 < size || 2*hole + 1 < size) { 
      //checks for invalid right child
      if (2*hole + 2 > size) { 
        //compare to left child
        if (item.compareTo(arr[2*hole + 1]) > 0) { 
          //this is the new hole
          hole = 2*hole + 1; 
        }
      }
      //checks for valid right child
      else if (2*hole + 2 < size){ 
        //if left is less than right
        if (arr[2*hole + 1].compareTo(arr[2*hole+2]) <= 0) { 
          //compares left to value
          if (item.compareTo(arr[2*hole + 1]) > 0) { 
            //this is the new hole
            newHole = 2*hole + 1; 
          }
        }
        else {
          //compares right child to value
          if (item.compareTo(arr[2*hole + 2]) > 0) { 
            //this is the new hole
            newHole = 2*hole + 2; 
          }
        }
      }
      else {
        //checks if value is greater than left child
        if (item.compareTo(arr[2*hole + 1]) > 0) { 
          //this is the new hole
          newHole = 2*hole + 1; 
        }
      }
    }
    return newHole;
  }
  //postcondition:  returns index of new hole
 
  /*MERGESORT ALGORITHM*/
  //precondition:  supply instantiated array 
  // of size many elements
  public static <Type extends Comparable<? super Type>> 
  void mergeSort(Type[] arr, int size) {
    mergesort(arr, 0, size - 1);
  }
  //postcondition:  returns parameter argument 
  // arr in ascending sorted order
 
  //precondition:  supply instantiated array of 
  // size many elements, index of first element, 
  // and index of last element
  private static <Type extends Comparable<? super Type>> 
  void mergesort(Type[] arr, int first, int last) {
    if (first < last) {
      int middle = (first + last)  / 2;
      //recursive mergesort on first half
      mergesort(arr, first, middle); 
      //recursive mergesort on second half
      mergesort(arr, middle + 1, last); 
      //merge both halves
      mergeSortedHalves(arr, first, middle, last);
    }
  }
  //postcondition:  returns parameter argument 
  // array in ascending sorted order
 
  //precondition:  supply instantiated array, 
  // index of left element, index of middle 
  // element, and index of right element
  private static <Type extends Comparable<? super Type>> 
  void mergeSortedHalves(Type[] arr, int left, int middle, int right) {
    Type[] temp = (Type[])new Comparable[right - left + 1];
 
    int index1 = left;
    int index2 = middle + 1;
    int index = 0;
    //while both halves have elements
    while (index1 <= middle && index2 <= right) {
      if (arr[index1].compareTo(arr[index2]) <= 0) {
        temp[index] = arr[index1];
        index1++;
      }
      else {
        temp[index] = arr[index2];
        index2++;
      }
      index++;
    }
    //if upper while loop finished but first half 
    // has more elements
    if (index1 <= middle) {
      while (index1 <= middle) {
        temp[index] = arr[index1];
        index++;
        index1++;
      }
    }
    //if upper while loop finished but second half 
    // has more elements
    else if (index2 <= right) {
      while (index2 <= right) {
        temp[index] = arr[index2];
        index++;
        index2++;
      }
    }
    System.arraycopy(temp, 0, arr, left, temp.length);
  }
  //postcondition:  returns a single sorted array from 
  // sub array[left to middle] and sub array[middle to right]
 
 
  /*QUICKSORT ALGORITHM*/
  //precondition:  supply instantiated array of 
  // size many elements
  public static <Type extends Comparable<? super Type>> 
  void quickSort(Type[] arr, int size) {
    quickSort(arr, 0, size - 1);
  }
  //postcondition:  returns parameter argument array 
  // in ascending sorted order
 
  //precondition:  supply instantiated array, 
  // index of first element, and index of last element
  private static <Type extends Comparable<? super Type>> 
  void quickSort(Type[] arr, int first, int last) {
    if (first < last) {
      setPivotToEnd(arr, first, last);
      int pivotIndex = splitList(arr, first, last);
      quickSort(arr, first, pivotIndex - 1);
      quickSort(arr, pivotIndex + 1, last);
    }
  }
  //postcondition:  returns parameter argument array 
  // in ascending sorted order
 
  //precondition:  supply instantiated array, index 
  // of left element, and index of right element
  private static <Type extends Comparable<? super Type>> 
  void setPivotToEnd(Type[] arr, int left, int right) {
    int center = (left + right) / 2;
    Type temp;
 
    if (arr[center].compareTo(arr[left]) < 0) {
      temp = arr[center];
      arr[center] = arr[left];
      arr[left] = temp;
    }
    if (arr[right].compareTo(arr[left]) < 0) {
      temp = arr[right];
      arr[right] = arr[left];
      arr[left] = temp;
    }
    if (arr[center].compareTo(arr[right]) < 0) {
      temp = arr[center];
      arr[center] = arr[right];
      arr[right] = temp;
    }
  }
  //postcondition:  median of three values at left, 
  // right, and center is swapped to right index
 
  //precondition:  supply instantiated array, index 
  // of left element, and index of right element
  private static <Type extends Comparable<? super Type>> 
  int splitList(Type[] arr, int left, int right) {
    int indexL = left;
    int indexR = right - 1;
    Type pivot = arr[right];
    Type temp;
 
    while (indexL <= indexR) { 
      //while indices have not run over
      while (arr[indexL].compareTo(pivot) < 0) { 
        //find element greater than pivot
        indexL++;
      }
      while (indexL <= indexR && arr[indexR].compareTo(pivot) > 0) { 
        //find element less than pivot
        indexR--;
      }
      if (indexL <= indexR) {
        //swap the two values
        temp = arr[indexL];
        arr[indexL] = arr[indexR];
        arr[indexR] = temp;
        indexL++;
        indexR--;
      }
    }
    //if indexL is not the right index swap them
    if (indexL != right) {
      temp = arr[indexL];
      arr[indexL] = arr[right];
      arr[right] = temp;
    }
    return indexL;
  }
  //postcondition:  returns index of final pivot position
}