import java.util.*;

public class Sorting {

	public static final int MAX = 256000;

	/** Main method. */
	static public void main(String[] args) {
		List<Integer> randlist = new ArrayList<Integer>(MAX); // original
		Random generaator = new Random();
		int maxKey = Math.min(1000, (MAX + 32) / 16);
		for (int i = 0; i < MAX; i++) {
			randlist.add(new Integer(generaator.nextInt(maxKey)));
		}

		int rightLimit = randlist.size() / 16;

		// Start a competition
		for (int round = 0; round < 4; round++) {
			rightLimit = 2 * rightLimit;
			System.out.println("\nLength: " + String.valueOf(rightLimit));

			List<Integer> copy1 = new ArrayList<Integer>(randlist);
			long stime = new Date().getTime();
			insertionSort(copy1, 0, rightLimit);
			long ftime = new Date().getTime();
			int diff = new Long(ftime - stime).intValue();
			System.out.println("\nInsertion sort");
			System.out.println("Time (ms): " + String.valueOf(diff));
			if (!checkOrder(copy1, 0, rightLimit))
				throw new RuntimeException("Wrong order!!!");
			List<Integer> copy2 = new ArrayList<Integer>(randlist);
			stime = new Date().getTime();
			biSort(copy2, 0, rightLimit);
			ftime = new Date().getTime();
			diff = new Long(ftime - stime).intValue();
			System.out.println("\nBinary insertion sort");
			System.out.println("Time (ms): " + String.valueOf(diff));
			if (!checkOrder(copy2, 0, rightLimit))
				throw new RuntimeException("Wrong order!!!");
			List<Pair> opairs = new ArrayList<Pair>(MAX);
			for (int i = 0; i < randlist.size(); i++) {
				opairs.add(new Pair(randlist.get(i), i));
			}
			biSort(opairs, 0, rightLimit);
			if (!checkStability(opairs, 0, rightLimit))
				throw new RuntimeException("Method not stable!");
			List<Integer> copy3 = new ArrayList<Integer>(randlist);
			stime = new Date().getTime();
			qsort(copy3, 0, rightLimit);
			ftime = new Date().getTime();
			diff = new Long(ftime - stime).intValue();
			System.out.println("\nQuicksort");
			System.out.println("Time (ms): " + String.valueOf(diff));
			if (!checkOrder(copy3, 0, rightLimit))
				throw new RuntimeException("Wrong order!!!");
			List<Integer> copy4 = new ArrayList<Integer>(randlist);
			Integer[] sarray = new Integer[rightLimit];
			sarray = (Integer[]) copy4.toArray(sarray);
			stime = new Date().getTime();
			Arrays.sort(sarray, 0, rightLimit);
			ftime = new Date().getTime();
			copy4 = Arrays.asList(sarray);
			diff = new Long(ftime - stime).intValue();
			System.out.println("\njava.util.Arrays");
			System.out.println("Time (ms): " + String.valueOf(diff));
			if (!checkOrder(copy4, 0, rightLimit))
				throw new RuntimeException("Wrong order!!!");
			List<Integer> copy5 = new ArrayList<Integer>(randlist);
			copy5 = copy5.subList(0, rightLimit);
			stime = new Date().getTime();
			Collections.sort(copy5);
			ftime = new Date().getTime();
			diff = new Long(ftime - stime).intValue();
			System.out.println("\njava.util.Collections");
			System.out.println("Time (ms): " + String.valueOf(diff));
			if (!checkOrder(copy5, 0, rightLimit))
				throw new RuntimeException("Wrong order!!!");
		}
	} // main()

	/**
	 * Sort a part of the list using quicksort method.
	 * 
	 * @param array
	 *            list
	 * @param l
	 *            starting index (included)
	 * @param r
	 *            ending index (excluded)
	 */
	static public <T extends Object & Comparable<? super T>> void qsort(
			List<T> array, int l, int r) {
		if (array.size() < 2)
			return;
		if ((r - l) < 2)
			return;
		int i = l;
		int j = r - 1;
		T x = array.get((i + j) / 2);
		do {
			while (array.get(i).compareTo(x) < 0)
				i++;
			while (x.compareTo(array.get(j)) < 0)
				j--;
			if (i <= j) {
				T tmp = array.get(i);
				array.set(i, array.get(j));
				array.set(j, tmp);
				i++;
				j--;
			}
		} while (i < j);
		if (l < j)
			qsort(array, l, j + 1); // recursion for left part
		if (i < r - 1)
			qsort(array, i, r); // recursion for right part
	} // qsort()

	/**
	 * Sort a part of the list using binary insertion sort method in a stable
	 * manner.
	 * 
	 * @param a
	 *            list
	 * @param left
	 *            starting position (included)
	 * @param right
	 *            ending position (excluded)
	 */
	static public <T extends Object & Comparable<? super T>> void biSort(
			List<T> a, int left, int right) {

		int mid, i, j;
		T v6ti;

		right = a.size() - 1;
		
		//binary searching
		for (i = left + 1; i < 
				left; i++) {

			v6ti = a.remove(i);
			mid = (right - left) / 2;
			if (v6ti.compareTo((T) a.get(mid)) < 0)
				right = mid - 1;
			
			if (v6ti.compareTo((T) a.get(mid)) > 0)

				left = mid + 1;

			if (a.size() < 2)
				return;
			if ((right - left) < 2)
				return;

			for (j = left; j < i; j++) {
				if(v6ti.compareTo(a.get(j))==0) ;
				if (v6ti.compareTo(a.get(j)) < 0)
					break;
			}
			a.add(j, v6ti); // insert v6ti to position j

		}

	}

	

	// TODO!!! Your code here!
	// biSort()

	/**
	 * 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 insertionSort(
			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.remove(i);
			int j;
			for (j = l; j < i; j++) {
				if (b.compareTo(a.get(j)) < 0)
					break;
			}
			a.add(j, b); // insert b to position j

		}
	} // insertionSort()

	/**
	 * Check whether a given interval in the list is ordered.
	 * 
	 * @param a
	 *            sorted (?) list.
	 * @param l
	 *            left index (included)
	 * @param r
	 *            right index (excluded)
	 * @return interval is ordered?
	 */
	static <T extends Object & Comparable<? super T>> boolean checkOrder(
			List<T> a, int l, int r) {
		if (a == null)
			throw new IllegalArgumentException();
		if (a.size() < 2)
			return true;
		if (l < 0 || r > a.size() || l >= r)
			throw new IllegalArgumentException();
		if (r - l < 2)
			return true;
		for (int i = l; i < r - 1; i++) {
			if (a.get(i).compareTo(a.get(i + 1)) > 0)
				return false;
		} // for
		return true;
	} // checkOrder()

	/** Is the list sorted in a stable manner. */
	static boolean checkStability(List<Pair> a, int l, int r) {
		if (a == null)
			throw new IllegalArgumentException();
		if (a.size() < 2)
			return true;
		if (l < 0 || r > a.size() || l >= r)
			throw new IllegalArgumentException();
		if (r - l < 2)
			return true;
		for (int i = l; i < r - 1; i++) {
			if (a.get(i).compareTo(a.get(i + 1)) > 0)
				return false;
			else if (a.get(i).compareTo(a.get(i + 1)) == 0) {
				// System.out.print("=");
				if (((Pair) a.get(i)).getSecundo() > ((Pair) a.get(i + 1))
						.getSecundo()) {
					System.out.println("Method is not stable. First error: "
							+ i + ". " + a.get(i) + " <--> " + (i + 1) + ". "
							+ a.get(i + 1));
					return false;
				}
			}
		} // for
		return true;
	}
}

/** Local class to test stability. */
class Pair implements Comparable<Pair> {

	private int primo;
	private int secundo;

	Pair(int a, int b) {
		primo = a;
		secundo = b;
	}

	public int getPrimo() {
		return primo;
	}

	public int getSecundo() {
		return secundo;
	}

	@Override
	public String toString() {
		return "(" + String.valueOf(primo) + "," + String.valueOf(secundo)
				+ ")";
	}

	public int compareTo(Pair o) {
		int esim = this.primo;
		int teine = ((Pair) o).primo;
		if (esim > teine)
			return 1;
		else if (esim < teine)
			return -1;
		else
			return 0;
	}
} // Pair