import java.util.*;

public class TreeSortMain
{
	public static void main (String[ ] args)
	{
		Integer[ ] intArray = {59,  46,  32,  80,  46,  55, 87, 43,  44,  81, 
		 		           95,  12,  17,  80,  75,  33,  40,  61,  16,  50};
				
		ArrayList<Integer> scores = new ArrayList<Integer>();
		for (int i = 0; i < intArray.length; i++)
			scores.add (intArray [i]);
		System.out.println (scores);		
		treeSort(scores);
		System.out.println (scores);		
	} // method main


	/**
	 *  Sorts a specified List object, according to the ordering given by
	 *  the compareTo method of the elements’ class.
 	 *  The worstTime(n) is O(n log n).
	 *
	 *  @param aList - the List object to be sorted.	 
	 *
	 */	 
	public static <E> void treeSort (List<E> aList)          
  	{
	      	TreeMap<E, Integer> aMap = new TreeMap<E, Integer>();

      		Integer value;

		for (E element : aList)
		{      		
          		value = aMap.get (element);
          		if (value == null)
              			aMap.put (element, 1);
          		else
              			aMap.put (element, value + 1); // boxing and unboxing
      		} // for each element in aList
      		aList.clear();

		for (Map.Entry<E, Integer> entry : aMap.entrySet())
			for (int i = 0; i < entry.getValue(); i++)
				aList.add (entry.getKey());      		
  	} // method treeSort

} // class TreeSortMain