import java.util.List;
import java.util.ArrayList;

/**
 * Class that contains static methods for sorting a List of comparable items.
 *   @author Dave Reed
 *   @version 9/23/08 
 */
public class Sorts {
    /**
     * Sorts (in place) the items in the list using selection sort
     *   @param list the list of comparable items to be sorted
     */
    public static <T extends Comparable<? super T>> void selectionSort(List<T> items) {    
        Sorts.selectionSortRange(items, 0, items.size()-1);
    }
    
    private static <T extends Comparable<? super T>> void selectionSortRange(List<T> items, int low, int high) {    
        for (int i = low; i < high; i++) {
            int minIndex = i;
            for (int j = i+1; j <= high; j++) {
                if (items.get(minIndex).compareTo(items.get(j)) > 0) {
                    minIndex = j;
                }
            }
            T temp = items.get(minIndex);
            items.set(minIndex, items.get(i));
            items.set(i, temp);
        }
    }
    
////////////////////////////////////////////////////////////////////////////
    
    /**
     * Sorts (in place) the items in the list using merge sort
     *   @param list the list of comparable items to be sorted
     */
    public static <T extends Comparable<? super T>>  void mergeSort(List<T> list) {
        Sorts.mergeSortRange(list, 0, list.size()-1);
    }
    
    private static <T extends Comparable<? super T>>  void mergeSortRange(List<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(List<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++;
            }
        }
    }
}