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

/**
   A utility class with sorting methods.

   @author Franck van Breugel
*/
public class Sort
{
    /**
       Insert the given element into the sorted list.

       @param element an element.
       @pre. element != null
       @param list a sorted list and list does not contain null
       @pre. !list.isEmpty()
    */
    private static <T extends Comparable<T>> void insert(T element, List<T> list)
    {
	if (element.compareTo(list.get(list.size() - 1)) >= 0)
	{
	    list.add(element);
	}
	else if (element.compareTo(list.get(0)) <= 0)
	{
	    list.add(0, element);
	}
	else
	{
	    int i = 1;
	    while (element.compareTo(list.get(i)) > 0)
	    {
		i++;
	    }
	    /*
	      element with index i is greater than or equal to the given element
	    */
	    list.add(i, element);
	}
    }

    /**
       Sorts the given list.

       @param list the list.
       @pre. list does not contain null
    */
    public static <T extends Comparable<T>> void insertion(List<T> list)
    {
	if (list.size() <= 1)
	{
	    // do nothing
	}
	else
	{
	    T first = list.remove(0);
	    Sort.insertion(list);
	    Sort.insert(first, list);
	}
    }

    /**
       Selects a smallest element of the given list.
       Returns the index of a smallest element.

       @param list the list.
       @pre. list.size() > 0 and list does not contain null
       @return the index of a smallest element of the list.
    */
    private static <T extends Comparable<T>> int select(List<T> list)
    {
	int selected = 0;
	for (int i = 1; i < list.size(); i++)
	{
	    if (list.get(selected).compareTo(list.get(i)) > 0)
	    {
		selected = i;
	    }
	}
	return selected;
    }

    /**
       Sorts the given list.

       @param list the list.
       @pre. list does not contain null
    */
    public static <T extends Comparable<T>> void selection(List<T> list)
    {
	if (list.size() <= 1)
	{
	    // do nothing
	}
	else
	{
	    T smallest = list.remove(Sort.select(list));
	    Sort.selection(list);
	    list.add(0, smallest);
	}
    }

    /**
       Returns a sorted copy of the given list.

       @param list the list.
       @pre. list does not contain null
       @return a sorted copy of the given list.
    */
    public static <T extends Comparable<T>> List<T> merge(List<T> list)
    {
	List<T> sorted;
	if (list.size() <= 1)
	{
	    sorted = new ArrayList<T>(list);
	}
	else
	{
	    List<T> first = new ArrayList<T>((list.size() + 1) / 2);
	    List<T> rest = new ArrayList<T>(list);
	    for (int i = 0; i < (list.size() + 1) / 2; i++)
	    {
		first.add(rest.remove(0));
	    }	
	    sorted = Sort.merge(Sort.merge(first), Sort.merge(rest));
	}
	return sorted;
    }

    /**
       Returns the merge of the given two lists.
       The given lists are altered by the merge.

       @param first a list.
       @pre. first does not contain null
       @param second a list.
       @pre. second does not contain null
       @return the merge of the given two lists.
    */
    private static <T extends Comparable<T>> List<T> merge(List<T> first, List<T> second)
    {
	List<T> merge = new ArrayList<T>(first.size() + second.size());
	while (!first.isEmpty() && !second.isEmpty())
	{
	    if (first.get(0).compareTo(second.get(0)) < 0)
	    {
		merge.add(first.remove(0));
	    }
	    else
	    {
		merge.add(second.remove(0));
	    }
	}
	merge.addAll(first);
	merge.addAll(second);
	return merge;
    }

    /**
       Returns a sorted copy of the given list.

       @param list the list.
       @pre. list does not contain null
       @return a sorted copy of the given list.
    */
    public static <T extends Comparable<T>> List<T> quick(List<T> list)
    {
	List<T> sorted;
	if (list.size() <= 1)
	{
	    sorted = new ArrayList<T>(list);
	}
	List<T> smaller = new ArrayList<T>();
	List<T> greater = new ArrayList<T>();
	T middle = list.get(0);
	for (int i = 1; i < list.size(); i++)
	{
	    if (middle.compareTo(list.get(i)) > 0)
	    {
		smaller.add(list.get(i));
	    }
	    else
	    {
		greater.add(list.get(i));
	    }
	}
	sorted = Sort.quick(smaller);
	List<T> rest = Sort.quick(greater);
	sorted.add(middle);
	sorted.addAll(rest);
	return sorted;
    }
}