public class SlowSort {
	
	private static void slowSort(int[] array) {
		slowSort(array, 0, array.length-1);
	}
	
	// Hilfsmethode (gleicher Name, andere Signatur)
	private static void slowSort(int[] array, int from, int to) {
		if (from >= to)  // Rekursionsanker (fertig sortiert)
			return;
		
		int middle = from + (to-from)/2;  // entspricht (from+to)/2 (nur besser)

		slowSort(array, from, middle);  // 1.
		slowSort(array, middle+1, to);  // 2.
		
		// 3. Maximum nach hinten tauschen (falls array[to] nocht nicht Max.)
		if (array[middle] > array[to]) {  // anderenfalls nichts nötig
			int tmp = array[to];
			array[to] = array[middle];  // Maximum wird zugewiesen
			array[middle] = tmp;
		}
		
		slowSort(array, from, to-1);  // 4.
	}
	
	
	private static void evenSlowerSort(int[] array) {
		evenSlowerSort(array, 0, array.length-1);
		
	}

	// Hilfsmethode (gleicher Name, andere Signatur)
	private static void evenSlowerSort(int[] array, int from, int to) {
		if (from >= to)
			return;

		int third1 = from + (int)(1.0/3 * (to-from));
		int third2 = from + (int)(2.0/3 * (to-from));
		
		evenSlowerSort(array, from, third1);    // 1.
		evenSlowerSort(array, third1+1, third2);  // 2.
		evenSlowerSort(array, third2+1, to);        // 3.
		
		if (array[third1] > array[to] && array[third1] > array[third2]) {
			int tmp = array[third1];
			array[third1] = array[to];
			array[to] = tmp;
		}
		else if (array[third2] > array[to]) {  // Hälfte 2 hat Größtes
			int tmp = array[third2];
			array[third2] = array[to];
			array[to] = tmp;
		}
		
		evenSlowerSort(array, from, to-1);
	}
	
	
	public static void main(String[] args) {		
		long timeSlow = 0;
		long timeSlower = 0;
		
		int runs = 10;
		int maxSize = 30;
		
		for (int i = 0; i < runs; i++) {
			int laenge = (int) (maxSize * Math.random());
			int[] arr1 = new int[laenge];
			int[] arr2 = new int[laenge];
			
			for (int j = 0; j < laenge; j++) {
				arr1[j] = arr2[j] = (int) (2000 * Math.random());
			}
	
			//arr1 = new int[] {};
			//arr2 = new int[] {3, 2, };
			
			System.out.println("Zufälliges Array:");
			System.out.println(java.util.Arrays.toString(arr1));
			
			long start, time;
			start = System.nanoTime();
			slowSort(arr1);
			time = System.nanoTime() - start;
			timeSlow += time;
			System.out.println("Sortiert mittels SlowSort:");
			System.out.println(java.util.Arrays.toString(arr1));
			
			start = System.nanoTime();
			evenSlowerSort(arr2);
			time = System.nanoTime() - start;
			timeSlower += time;
			System.out.println("Sortiert mittels EvenSlowerSort:");
			System.out.println(java.util.Arrays.toString(arr2));
		}
		
		System.out.println("Slow: " + timeSlow/runs);
		System.out.println("Slower: " + timeSlower/runs);
	}
	
}