import java.util.ArrayList;
import java.util.Collections;

/**
 * A collection of static sorting routines.
 *   @author Dave Reed
 *   @version 8/15/13
 */
public class Sorts {

  /**
   * Sorts the items in the list using insertion sort
   *   @param items the list to be sorted (in place)
   */
  public static <T extends Comparable<? super T>> void insertionSort(ArrayList<T> items) {
    for (int i = 1; i < items.size(); i++) {        // for each index i,
      T itemToPlace = items.get(i);                 //   save the value at index i
      int j = i;                                    //   starting at index i,
      while (j > 0 && itemToPlace.compareTo(items.get(j-1)) < 0) {
          items.set(j, items.get(j-1));             //     shift values to the right
          j--;                                      //     until find spot for the value
      }
      items.set(j, itemToPlace);                    //   store the value in its spot
    }
  }
 
////////////////////////////////////////////////////////////////////////////
    
  /**
   * Sorts the items in the list using selection sort
   *   @param items the list to be sorted (in place)
   */
  public static <T extends Comparable<? super T>> void selectionSort(ArrayList<T> items) {
    for (int i = 0; i < items.size()-1; i++) {      // for each index i,
      int indexOfMin = i;                           //   find the ith smallest item
      for (int j = i+1; j < items.size(); j++) {    
        if (items.get(j).compareTo(items.get(indexOfMin)) < 0) {
          indexOfMin = j;
        }
      }
    
      T temp = items.get(i);                        //   swap the ith smallest
      items.set(i, items.get(indexOfMin));          //   item into position i
      items.set(indexOfMin, temp);              
    }
  }
  
  ////////////////////////////////////////////////////////////////////////////
    
    /**
     * Sorts the items in the list using merge sort
     *   @param list the list of comparable items to be sorted (in place)
     */
    public static <T extends Comparable<? super T>>  void mergeSort(ArrayList<T> list) {
        Sorts.mergeSortRange(list, 0, list.size()-1);
    }
    
    private static <T extends Comparable<? super T>>  void mergeSortRange(ArrayList<T> items,
                                           int low, int high) {
        if (low < high) {
            int middle = (low + high)/2;
            Sorts.mergeSortRange(items, low, middle);
            Sorts.mergeSortRange(items, middle+1, high);
            Sorts.merge(items, low, high);
        }
    }
    
    private static <T extends Comparable<? super T>> void merge(ArrayList<T> items,
                                           int low, int high) {
        ArrayList<T> copy = new ArrayList<T>();
        for (int i = low; i <= high; i++) {
            copy.add(items.get(i));
        }
        
        int front1 = 0;
        int front2 = (copy.size()+1)/2;
        
	for (int i = low; i <= high; i++) {
            if (front2 >= copy.size() || 
                (front1 < ((copy.size()+1)/2) &&
                 copy.get(front1).compareTo(copy.get(front2)) <= 0)) {
                items.set(i, copy.get(front1));
                front1++;
            }
            else {
                items.set(i, copy.get(front2));
                front2++;
            }
        }
    }
}