import java.util.*;

public class ColorMethods {

   enum Color {red, green, blue};

   static final int MAX = 256000; // adjust this according to your computer

   public static void reorder (List<Color> balls) {
      // TODO!!! Your method here!
   }

   /**
    * Sort a part of the list of comparable elements using insertion sort.
    * @param a list
    * @param l starting position (included)
    * @param r ending position (excluded)
    */
   static public <T extends Object & Comparable<? super T>> void 
    iSort (List<T> a, int l, int r) {
      if (a.size() < 2) return;
      if ((r-l)<2) return;
      for (int i = l+1; i < r; i++) {
         T b = a.get (i);
         int j;
         for (j=i-1; j >= l; j--) {
            if (a.get (j).compareTo (b) <= 0) break;
            a.set (j+1, a.get (j));
         }
         a.set (j+1, b);
      }
   }

   static void check (List<Color> balls, int r, int g, int b) {
      int len = balls.size();
      if (r<0 || g<0 || b<0 || len != r+g+b)
         throw new IllegalArgumentException ("error in parameters"); 
      if (len == 0)
         return;
      for (int i=0; i < r; i++)
         if (balls.get (i) != Color.red)
            throw new IllegalArgumentException 
               ("not ordered! red " + i + " was " + balls.get (i));
      for (int i=r; i < r+g; i++)
         if (balls.get (i) != Color.green)
            throw new IllegalArgumentException
               ("not ordered! green " + i + " was " + balls.get (i));
      for (int i=r+g; i < len; i++)
         if (balls.get (i) != Color.blue)
            throw new IllegalArgumentException
               ("not ordered! blue " + i + " was " + balls.get (i));
   }

   public static void main (String[] param) {
      List<Color> orig = new ArrayList<Color> (MAX);
      int rCount, gCount, bCount;
      for (int i=0; i < MAX; i++) {
         double rnd = Math.random();
         if (rnd < 1./3.) orig.add (Color.red);
         else  if (rnd > 2./3.) orig.add (Color.blue);
         else orig.add (Color.green);
      }
      int rightLimit = orig.size()/16;
      long t0, t1;
      List<Color> a1, a2, a3;
      for (int round=0; round < 4; round++) {
         rightLimit *= 2;  // number of elements in current round
         a1 = new ArrayList<Color> (orig);
         a1 = a1.subList (0, rightLimit);
         rCount = 0;  gCount = 0;  bCount = 0;
         for (Color elem: a1) {
            if (elem==Color.red) rCount++;
            else if (elem==Color.green) gCount++;
            else if (elem==Color.blue) bCount++;
            else throw new IllegalArgumentException (" wrong color " + elem);
         }
         System.out.println();
         System.out.print ("Insertion sort");
         System.out.print ("\tn = " + a1.size());
         t0 = System.currentTimeMillis();
         iSort (a1, 0, a1.size());
         t1 = System.currentTimeMillis();
         check (a1, rCount, gCount, bCount);
         System.out.println ("\ttime = " + (t1-t0) );
         a2 = new ArrayList<Color> (orig);
         a2 = a2.subList (0, rightLimit);
         System.out.print ("Java API sort");
         System.out.print ("\tn = " + a2.size());
         t0 = System.currentTimeMillis();
         Collections.sort (a2);
         t1 = System.currentTimeMillis();
         check (a2, rCount, gCount, bCount);
         System.out.println ("\ttime = " + (t1-t0) );
         a3 = new ArrayList<Color> (orig);
         a3 = a3.subList (0, rightLimit);
         System.out.print ("My method");
         System.out.print ("\tn = " + a3.size());
         t0 = System.currentTimeMillis();
         reorder (a3);
         t1 = System.currentTimeMillis();
         check (a3, rCount, gCount, bCount);
         System.out.println ("\ttime = " + (t1-t0) );
      }
   }
}