/*
 * VM arguments:
 *   -ea -server -Xms256m -Xmx256m
 */
 
/*
[620, 629, 922, 136, 511, 100, 770, 81, 353, 309, ...
      bubble (     1,000): 0.005250 sec
      select (     1,000): 0.003250 sec
   insertion (     1,000): 0.003250 sec
       shell (     1,000): 0.001250 sec
       merge (     1,000): 0.001250 sec
        heap (     1,000): 0.003250 sec
       heap2 (     1,000): 0.003500 sec
       radix (     1,000): 0.001250 sec
 Arrays.sort (     1,000): 0.001250 sec
      qsort1 (     1,000): 0.000750 sec
      qsort2 (     1,000): 0.000500 sec
 
[4675, 1070, 1354, 2406, 3371, 3518, 1171, 4722, 3076, 4376, ...
      bubble (     5,000): 0.071250 sec
      select (     5,000): 0.040250 sec
   insertion (     5,000): 0.019500 sec
       shell (     5,000): 0.000750 sec
       merge (     5,000): 0.001000 sec
        heap (     5,000): 0.002750 sec
       heap2 (     5,000): 0.000750 sec
       radix (     5,000): 0.000500 sec
 Arrays.sort (     5,000): 0.000750 sec
      qsort1 (     5,000): 0.000500 sec
      qsort2 (     5,000): 0.000750 sec
 
[4375, 2268, 9716, 7156, 6008, 6028, 614, 6534, 2892, 425, ...
       shell (    10,000): 0.003000 sec
       merge (    10,000): 0.002000 sec
        heap (    10,000): 0.001250 sec
       heap2 (    10,000): 0.001500 sec
       radix (    10,000): 0.000750 sec
 Arrays.sort (    10,000): 0.001500 sec
      qsort1 (    10,000): 0.001000 sec
      qsort2 (    10,000): 0.001250 sec
 
[823, 8976, 24160, 12372, 10026, 9719, 1755, 3531, 36687, 1195, ...
       shell (    50,000): 0.012250 sec
       merge (    50,000): 0.011500 sec
        heap (    50,000): 0.008000 sec
       heap2 (    50,000): 0.009500 sec
       radix (    50,000): 0.004000 sec
 Arrays.sort (    50,000): 0.008000 sec
      qsort1 (    50,000): 0.007500 sec
      qsort2 (    50,000): 0.007500 sec
 
[39935, 54239, 72967, 72529, 8653, 68693, 94704, 16256, 47284, 23651, ...
       shell (   100,000): 0.025500 sec
       merge (   100,000): 0.023750 sec
        heap (   100,000): 0.017000 sec
       heap2 (   100,000): 0.021000 sec
       radix (   100,000): 0.006750 sec
 Arrays.sort (   100,000): 0.018000 sec
      qsort1 (   100,000): 0.015000 sec
      qsort2 (   100,000): 0.016250 sec
 
[177751, 456417, 277005, 330854, 12915, 252980, 464598, 332745, 335903, 107469, ...
       shell (   500,000): 0.145250 sec
       merge (   500,000): 0.135000 sec
        heap (   500,000): 0.092500 sec
       heap2 (   500,000): 0.122250 sec
       radix (   500,000): 0.034750 sec
 Arrays.sort (   500,000): 0.100250 sec
      qsort1 (   500,000): 0.081500 sec
      qsort2 (   500,000): 0.088250 sec
 
[561208, 302967, 214794, 85848, 679732, 21686, 34697, 618287, 114928, 813398, ...
       shell ( 1,000,000): 0.314000 sec
       merge ( 1,000,000): 0.274750 sec
        heap ( 1,000,000): 0.197250 sec
       heap2 ( 1,000,000): 0.285000 sec
       radix ( 1,000,000): 0.071500 sec
 Arrays.sort ( 1,000,000): 0.209000 sec
      qsort1 ( 1,000,000): 0.170750 sec
      qsort2 ( 1,000,000): 0.186250 sec
 
[1059437, 1267649, 4675059, 1858172, 981712, 1672942, 4946791, 2659468, 1158464, 428233, ...
       shell ( 5,000,000): 1.807000 sec
       merge ( 5,000,000): 1.563250 sec
        heap ( 5,000,000): 1.148250 sec
       heap2 ( 5,000,000): 2.530750 sec
       radix ( 5,000,000): 0.352250 sec
 Arrays.sort ( 5,000,000): 1.165250 sec
      qsort1 ( 5,000,000): 0.937250 sec
      qsort2 ( 5,000,000): 1.032750 sec
 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
       shell (    80,000): 0.004500 sec
       merge (    80,000): 0.010750 sec
        heap (    80,000): 0.013250 sec
       heap2 (    80,000): 0.015250 sec
       radix (    80,000): 0.005250 sec
 Arrays.sort (    80,000): 0.004500 sec
      qsort1 (    80,000): 5.507500 sec
      qsort2 (    80,000): 0.003750 sec
 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
       shell (    80,000): 0.004500 sec
       merge (    80,000): 0.011000 sec
        heap (    80,000): 0.014000 sec
       heap2 (    80,000): 0.005250 sec
       radix (    80,000): 0.005750 sec
 Arrays.sort (    80,000): 0.000500 sec
 
*/
import java.util.Arrays;
import java.util.Random;
 
public class SortingAlgorithms {
	// ----------------------------------------------------------------
	// Utilities
	// ----------------------------------------------------------------
	private static final Random RANDOM = new Random();
 
	private static void swap(int[] ns, int i, int j) {
		int tmp = ns[j];
		ns[j] = ns[i];
		ns[i] = tmp;
	}
 
	private static int randint(int min, int max) {
		assert min < max;
		return min + RANDOM.nextInt(max-min+1);
	}
 
	public static int[] makeNumbers(int n) {
		int[] ns = new int[n];
		for (int i = 0; i < ns.length; i++) ns[i] = i;
		return ns;
	}
 
	public static int[] makeRandomNumbers(int n) {
		int[] ns = makeNumbers(n);
		for (int i = 0; i < ns.length; i++) swap(ns, i, randint(0, ns.length-1));
		return ns;
	}
 
	private static void validate(int[] ns, int[] result) {
		for (int i = 1; i < result.length; i++) {
			assert (result[i-1]+1 == result[i]) || 
			       (result[i-1] == result[i] && result[i] == ns[i]) : 
				(i-1) + ":" + result[i-1] + " " + i + ":" + result[i];
		}
	}
 
	// ----------------------------------------------------------------
	// Algorithms
	// ----------------------------------------------------------------
	private static interface SortAlgorithm {
		public void sort(int[] ns);
		public String name();
	}
 
	private static class BubbleSort implements SortAlgorithm {
		public String name() { return "bubble"; }
		public void sort(int[] ns) {
			for (int n = ns.length; n >= 2; n--) {
				for (int i = 1; i < n; i++) {
					if (ns[i] < ns[i-1]) swap(ns, i, i-1);
				}
			}
		}
	}
 
	private static class InsertionSort implements SortAlgorithm {
		public String name() { return "insertion"; }
		public void sort(int[] ns) {
			for (int i = 1; i < ns.length; i++) {
				int j, t = ns[i];
				for (j = i; j >= 1 && ns[j-1] > t; j--) ns[j] = ns[j-1];
				ns[j] = t;
			}
		}
	}
 
	private static class ShellSort implements SortAlgorithm {
		public String name() { return "shell"; }
		public void sort(int[] ns) {
			int step = ns.length/2;
			while (step > 0) {
				for (int i = step; i < ns.length; i++) {
					int j, t = ns[i];
					for (j = i; j >= step && ns[j-step] > t; j -= step) ns[j] = ns[j-step];
					ns[j] = t;
				}
				step = step == 2 ? 1 : (int)Math.round(step / 2.2);
			}
		}
	}
 
	private static class MergeSort implements SortAlgorithm {
		public String name() { return "merge"; }
 
		public void sort(int[] ns) {
			sort(ns, new int[ns.length], 0, ns.length-1);
		}
 
		private void merge(int[] ns, int[] tmp, int l, int m, int u) {
			int left = l, right = m+1;
 
			for (int i = l; i <= u; i++) {
				if (left <= m) {
					int t = ns[left];
					if (right > u || ns[right] > t) {
						tmp[i] = t; left++;
						continue;
					}
				}
				tmp[i] = ns[right++];
			}
			System.arraycopy(tmp, l, ns, l, u-l+1);
		}
 
		private void sort(int[] ns, int[] tmp, int l, int u) {
			if (l >= u) return;
			int m = (l+u)/2;
			assert m != u;
			assert m+1 != l;
			sort(ns, tmp, l, m);
			sort(ns, tmp, m+1, u);
			merge(ns, tmp, l, m, u);
		}
	}
 
	// ----------------------------------------------------------------
	// Selection, Heap
	// ----------------------------------------------------------------
	private static class SelectionSort implements SortAlgorithm {
		public String name() { return "select"; }
		public void sort(int[] ns) {
			for (int i = 0; i < ns.length; i++) {
				int min = i;
				for (int j = i; j < ns.length; j++) {
					if (ns[j] < ns[min]) min = j;
				}
				swap(ns, i, min);
			}
		}
	}
 
	private static class HeapQueue {
		private final int[] elements;
		private int size = 0;
 
		public HeapQueue(int capacity) {
			this.elements = new int[capacity+1];
		}
 
		public void insert(int v) {
			if (size == elements.length-1) 
				throw new ArrayIndexOutOfBoundsException(size);
			size++;
			this.elements[size] = v;
			shiftup(size);
		}
 
		public int remove() {
			if (size == 0) 
				throw new ArrayIndexOutOfBoundsException(size);
			int min = elements[1];
			elements[1] = elements[size--];
			shiftdown(1);
			return min;
		}
 
		private void shiftup(int n) {
			assert n > 0 && n <= size;
			int i = n;
			for (;;) {
				if (i == 1) break;
				int p = n/2;
				if (elements[i] >= elements[p]) break;
				swap(elements, i, p);
				i = p;
			}
		}
 
		private void shiftdown(int n) {
			assert n > 0;
			int i = n;
			for (;;) {
				int c = i*2; /* leftchild */
				if (c > size) break;
				if (c+1 <= size && elements[c+1] < elements[c]) c += 1;
				if (elements[c] >= elements[i]) break;
				swap(elements, i, c);
				i = c;
			}
		}
	}
 
	private static class HeapSort implements SortAlgorithm {
		public String name() { return "heap"; }
		public void sort(int[] ns) {
			final HeapQueue queue = new HeapQueue(ns.length);
			for (int i = 0; i < ns.length; i++) queue.insert(i);
			for (int i = 0; i < ns.length; i++) ns[i] = queue.remove();
		}
	}
 
	private static class HeapSort2 implements SortAlgorithm {
		public String name() { return "heap2"; }
		public void sort(int[] ns) {
			for (int i = 1; i < ns.length; i++) shiftup(ns, i, i+1);
			for (int i = ns.length-1; i >= 1; i--) {
				swap(ns, 0, i);
				shiftdown(ns, 0, i);
			}
		}
 
		private void shiftup(int[] ns, int n, int size) {
			int i = n;
			while (i > 0) {
				int p = (i+1)/2-1;
				if (ns[p] > ns[i]) break;
				swap(ns, i, p);
				i = p;
			}
		}
 
		private void shiftdown(int[] ns, int n, int size) {
			int i = n;
			for (;;) {
				int c = (i+1)*2-1; /* left */
				if (c >= size) break;
				if (c+1 < size && ns[c+1] > ns[c]) c++;
				if (ns[i] >= ns[c]) break;
				swap(ns, i, c);
				i = c;
			}
		}
	}
 
	/**
	 * Fast Radix Sort for unsigned 32 bit integer elements
	 */
	private static class RadixSort implements SortAlgorithm {
		public String name() { return "radix"; }
 
		public void sort(int[] ns) {
			int[] is = new int[17];
			int[] temp = new int[ns.length];
 
			for (int radix = 0; radix < 8; radix++) {
 
				// base indexes
				for (int i = 0; i < ns.length; i++) {
					int bits = (ns[i]>>(radix*4))&15;
					is[bits+1]++;
				}
				for (int i = 1; i < 17; i++) is[i] += is[i-1];
 
				for (int i = 0; i < ns.length; i++) {
					int bits = (ns[i]>>(4*radix))&15;
					temp[is[bits]++] = ns[i];
				}
				int[] t = temp; temp = ns; ns = t;
				Arrays.fill(is, 0);
			}
		}
	}
 
 
	// ----------------------------------------------------------------
	// Quicksort
	// ----------------------------------------------------------------
	private static class JavaUtilArraysSort implements SortAlgorithm {
		public String name() { return "Arrays.sort"; }
		public void sort(int[] ns) {
			Arrays.sort(ns);
		}
	}
 
	private static class QuickSort1 implements SortAlgorithm {
		public String name() { return "qsort1"; }
		public void sort(int[] ns) { qsort(ns, 0, ns.length-1); }
		private static void qsort(int[] ns, int l, int u) {
			if (l >= u) return;
			int t = ns[l], m = l;
			for (int i = l+1; i <= u; i++) {
				if (ns[i] < t) swap(ns, ++m, i);
			}
			swap(ns, l, m);
			qsort(ns, l, m-1);
			qsort(ns, m+1, u);
		}
	}
 
	private static class QuickSort2 implements SortAlgorithm {
		private static final int CUTOFF = 50;
		private static final SortAlgorithm INSSORT = new InsertionSort();
 
		public String name() { return "qsort2"; }
		public void sort(int[] ns) {
			qsort(ns, 0, ns.length-1);
			INSSORT.sort(ns);
		}
		private static void qsort(int[] ns, int l, int u) {
			if ((u-l) <= CUTOFF) return;
 
			swap(ns, l, randint(l, u));
			int t = ns[l], i = l, j = u+1;
			for (;;) {
				do { i++; } while (i <= u && ns[i] < t);
				do { j--; } while (ns[j] > t);
				if (i > j) break;
				swap(ns, i, j);
			}
			swap(ns, l, j);
			qsort(ns, l, j-1);
			qsort(ns, j+1, u);
		}
	}
 
	// ----------------------------------------------------------------
	// Main
	// ----------------------------------------------------------------
	private static final int SAMPLES = 4;
 
	private static void printSummary(int[] ns) {
		System.out.print('[');
		int i;
		for (i = 0; i < 10 && i < ns.length; i++) {
			System.out.print(ns[i]);
			if (i < ns.length-1) System.out.print(", ");
		}
		if (i == ns.length) {
			System.out.println("]");
		} else {
			System.out.println("...");
		}
	}
 
 
	public static void measure(final SortAlgorithm algorithm, int[] ns) {
		double elapsed = 0;
		final int[] copy = new int[ns.length];
 
		for (int i = 0; i < SAMPLES; i++) {
			System.arraycopy(ns, 0, copy, 0, copy.length);
 
			long millis = System.currentTimeMillis();
			algorithm.sort(copy);
			millis = System.currentTimeMillis() - millis;
			elapsed += millis/1000.0;
			validate(ns, copy);
		}
		System.out.printf("%12s (%,10d): %.6f sec\n", algorithm.name(), ns.length, elapsed/SAMPLES);
	}
 
	public static void measureAll(int[] ns) {
		printSummary(ns);
		if (ns.length < 10000) {
			measure(new BubbleSort(), ns);
			measure(new SelectionSort(), ns);
			measure(new InsertionSort(), ns);
		}
		measure(new ShellSort(), ns);
		measure(new MergeSort(), ns);
		measure(new HeapSort(), ns);
		measure(new HeapSort2(), ns);
		measure(new RadixSort(), ns);
		measure(new JavaUtilArraysSort(), ns);
		measure(new QuickSort1(), ns);
		measure(new QuickSort2(), ns);
		System.out.print('\n');
	}
 
	public static void main(String[] args) {
		for (int i = 0, n = 1000; n <= 5000000; n *= (i&1)==0?5:2, i++) {
			measureAll(makeRandomNumbers(n));
		}
 
		int[] ns = makeNumbers(80000);
		measureAll(ns);
		Arrays.fill(ns, 1);
		measureAll(ns);
	}
 
}