// Copyright(c) 2006, Shinichi Morishita. All Rights Reserved.

import java.util.Date;

public class Chapter2_Sorting {
	
	public static void insertionSort(int[] target){
		int n = target.length;
		for(int i = 1; i < n; i++){
			int v = target[i];
			int j;
			for(j = i; 0 < j && v < target[j-1]; j--) 
				target[j] = target[j-1];
			target[j] = v;
		}
	}
	
	public static void mergeSort( int[] target ){ // target != null.
		// Used for storing partially sorted lists.
		int[] tmp = new int[target.length]; 
		mergeRecursion(target, tmp, 0, target.length-1);
	}
	public static void mergeRecursion( int[] target, int[] tmp, int left, int right ){
		if(left < right){
			int middle = (right+left)/2;
			mergeRecursion(target, tmp, left, middle);     // Sort the left half.
			mergeRecursion(target, tmp, middle+1, right);  // Sort the right half.
	
			int i = left;      // i scans the sorted left half.
			int j = middle+1;  // j scans the sorted right half.
			int k;
			// Put the sorted list into array tmp temporarily.
			for(k=left; i <= middle && j <= right; k++){
				if(target[i] <= target[j]){ tmp[k] = target[i];  i++; }
				else{            			tmp[k] = target[j];  j++; }
			}
			// Append the remaining sorted sublist to the end of tmp.
			for(; j <= right;  k++){ tmp[k] = target[j]; j++; }
			for(; i <= middle; k++){ tmp[k] = target[i]; i++; }
			// Copy the sorted list from array tmp to array target.
			for(k = left; k <= right; k++ ) target[k] = tmp[k];
		}
	}	

	public static void heapSort(int[] target){ // target != null.
		int heapSize = target.length;
		int[] heap = new int[heapSize];		
		// Insert all elements in the target array into the heap.
		for(int i=0; i<heapSize; i++)  upheap(heap, i, target[i]);
		// Remove the element at the root node one by one.
		for(int i = 0; i < heapSize; i++){
			target[heapSize-1-i] = heap[0];    // Remove the largest element from the root.
			heap[0] = heap[heapSize-1-i];      // Move the last element in the heap to the root.
			downheap(heap, 0, heapSize-1-i-1); // Execute downheap to maintain the heap.
		}
	}

	public static void heapSort(int target[], int left, int right){
		int heapSize = right - left + 1;
		int[] heap = new int[heapSize];		
		// Insert all elements in the target array into the heap.
		for(int i=0; i<heapSize; i++)  upheap(heap, i, target[left+i]);
		// Remove the element at the root node one by one.
		for(int i = 0; i < heapSize; i++){
			target[right-i] = heap[0];    // Remove the largest element from the root.
			heap[0] = heap[heapSize-1-i];      // Move the last element in the heap to the root.
			downheap(heap, 0, heapSize-1-i-1); // Execute downheap to maintain the heap.
		}
	}
	
	public static void upheap(int[] heap, int leafPosition, int element){
		int child, parent;
		for( child = leafPosition, parent = (child-1)/2; 	// Initilization.
			 0 < child && element > heap[parent]; 
			 	// Confirm that the child has its parent and 
			 	// check if the element is greater than the parent's value.
			 child = parent, parent = (child-1)/2)	// Move child and parent upwards.
			heap[child] = heap[parent];	// Move the parent's value to the child.
		heap[child] = element;			// Locate the element in the proper position.
	}
	
	public static void downheap(int[] heap, int startPosition, int heapLast){
		int startValue = heap[startPosition];
		int parent = startPosition;
		while(parent*2+1 <= heapLast){ // The parent has the left child.
			int leftChild = parent*2+1;
			int greaterChild = leftChild; 
				// Assume that the left child has a greater value. 
			if( leftChild < heapLast && heap[leftChild] < heap[leftChild+1])
				// The parent has the right child whose value is greater.
				greaterChild = leftChild+1;
			if(startValue < heap[greaterChild]){ 
				// Push startValue downward.
				heap[parent] = heap[greaterChild];
				parent = greaterChild;
			}else break;	
				// Terminate the search for the proper position of startValue.
		}
		heap[parent] = startValue;
	}
	
	
	public static void randomQuickSort1(int[] target ) {
		randomQuickSort1(target, 0, target.length-1);
	}
	public static void randomQuickSort1(int[] target, int left, int right ) {
		if (left < right) {
			int i = partition(target, left, right);
						// i indicates the position of the pivot.
			randomQuickSort1(target, left, i - 1);
			randomQuickSort1(target, i + 1, right);
		}
	}
	
	public static void randomQuickSort2(int[] target ) {
		randomQuickSort2(target, 0, target.length-1);
	}	
	public static void randomQuickSort2(int[] target, int aLeft, int right) {
	     int left = aLeft;
	     while (left < right) {
	          int i = partition(target, left, right);
	          randomQuickSort2(target, left, i-1); 
	          left = i+1;             
	     }
	}

	public static void randomQuickSort3(int[] target ) {
		randomQuickSort3(target, 0, target.length-1);
	}	
	public static void randomQuickSort3(int[] target, int aLeft, int aRight) {
	     int left = aLeft; int right = aRight;
	     while (left < right) {
	          int i = partition(target, left, right);
	          if( i - left <= right - i ){ // The left interval is shorter.
	               randomQuickSort3(target, left, i-1); left=i+1;             
	          }else{                       // The right interval is shorter.
	               randomQuickSort3(target, i+1, right); 
	               right=i-1; 
	          }
	     }
	}

	public static void randomQuickSort4(int[] target, int minSize) {
		randomQuickSort4(target, 0, target.length-1, minSize);
	}	
	public static void randomQuickSort4(int[] target, int aLeft, int aRight, int minSize ) {
		int left = aLeft; int right = aRight;
		while (left + minSize < right) {
			int i = partition(target, left, right);	
			if( i - left <= right - i ){ // The left interval is shorter.
				randomQuickSort4(target, left, i - 1, minSize);
				left = i + 1;
			}else{                       // The right interval is shorter.
				randomQuickSort4(target, i + 1, right, minSize);
				right = i - 1;
			}		
		}
		// Insertion sort the target array of the range [left, right]
		for(int i = left+1; i <= right; i++){
			int v = target[i];
			int j;
			for(j = i; 0 < j && v < target[j-1]; j--) 
				target[j] = target[j-1];
			target[j] = v;
		}
	}
	
	public static void randomQuickSort5(int[] target, int minSize) {
		randomQuickSort5(target, 0, target.length-1, minSize);
	}		
	public static void randomQuickSort5(int[] target, int aLeft, int aRight, int minSize){
		randomQuickSort5sub(target, aLeft, aRight, minSize);
		insertionSort(target);
	}	
	public static void randomQuickSort5sub(int[] target, int aLeft, int aRight, int minSize ) {
		int left = aLeft; int right = aRight;
		while (left + minSize < right) {
			int i = partition(target, left, right);	
			if( i - left <= right - i ){ // The left interval is shorter.
				randomQuickSort5sub(target, left, i - 1, minSize);
				left = i + 1;
			}else{                       // The right interval is shorter.
				randomQuickSort5sub(target, i + 1, right, minSize);
				right = i - 1;
			}		
		}
	}

	public static void introspectiveSort(int[] target, int minSize){
		introspectiveSort(target, 0, target.length-1, minSize);
	}
	public static void introspectiveSort(int[] target, int aLeft, int aRight, int minSize){
		int depthLimit = 40; // Or, =(int)(Math.log(target.length) * 0.1);
		introspectiveSortSub(target, aLeft, aRight, minSize, depthLimit);
		insertionSort(target);
	}	
	public static void introspectiveSortSub(int[] target, int aLeft, int aRight, int minSize, int depthLimit) {
		int left = aLeft; int right = aRight;
		while (left + minSize < right) {
			if(depthLimit <= 0){
				heapSort(target, left, right); return; }
			depthLimit--;
			int i = partition(target, left, right);	
			introspectiveSortSub(target, left, i - 1, minSize, depthLimit);
			left = i + 1;	
		}
	}	
	
	public static int partition(int[] target, int left, int right ) {
		// Select a number between left and right at random .
		int random = selectRandomPosition(target, left, right);
		// Exchange target[right] and target[random].
		int tmp = target[right];  target[right] = target[random];  
		target[random] = tmp;
		
		int pivot = target[right];
		int i = left-1;  // i scans the array from the left.
		int j = right; 	 // j scans the array from the right. 		
		for (;;) {
			// Move from the left until hitting a value no less than the pivot. 
			for(i++; target[i] < pivot; i++){} 
			// Move from the right until hitting a value no greater than the pivot.
			for(j--; pivot < target[j] && i < j; j--){}
			if (i >= j)  break; 
			// Exchange target[i] and target[j]. 
			tmp = target[i];  target[i] = target[j];  target[j] = tmp;
		}
		// Exchange target[i] and target[right]. 
		tmp = target[i];  target[i] = target[right];  target[right] = tmp;
		return i;
	}	

	public static int selectRandomPosition(int[] target, int left, int right){
//		return singleton_random(left, right);
		return median_of_3randoms(target, left, right);
//		return median_of_3(target, left, right);
//		return right;
	}
	
	public static int singleton_random(int left, int right ) {
		return left + (int)Math.floor(Math.random()*(right-left+1));
	}
	
	public static int median_of_3randoms(int[] target, int left, int right ) {
		// Select the median of three random numbers.
		return median( target,	
				singleton_random(left, right),
				singleton_random(left, right),
				singleton_random(left, right));
	}
	
	public static int median_of_3(int[] target, int left, int right ) {
		// Select the median of the first(left), middle and last(right) elements.
		return median(target, left, (left+right)/2, right);
	}
	
	public static int median(int[] target, int r1, int r2, int r3){
		int m;
		if(target[r1] < target[r2])
			if(target[r2] < target[r3]) m = r2; 
			else{ if(target[r1] < target[r3]) m = r3; else m = r1; }
		else
			if(target[r2] > target[r3]) m = r2; 
			else{ if(target[r1] > target[r3]) m = r3; else m = r1; }
		return m;		
	}

	public static void ternarySplitQuickSort(int[] target) {
		ternarySplitQuickSort(target, 0, target.length-1);
	}
	public static void ternarySplitQuickSort(int[] target, int left, int right ) {
		if (left >= right) return;  // Skip processing if the array has only one element.		
		// Select a number between left and right at random .
		int random = selectRandomPosition(target, left, right);
		int pivot = target[random]; 
		int i = left;   // i scans the array from the left.
		int mi = left;  // Position available for the next pivot value.
		int j = right;  // j scans the array from the right.
		int mj = right; // Position available for the next pivot value.
		int tmp;
		for (;;) {
			// Move from the left until hitting a value greater than the pivot. 
			for(; i <= j && target[i] <= pivot; i++)
				if(target[i] == pivot){  // Move the pivot value to the left end.
					tmp = target[i]; target[i] = target[mi]; target[mi] = tmp; mi++; }
			// Move from the right until hitting a value less than the pivot.
			for(; i <= j && pivot <= target[j]; j--)
				if(target[j] == pivot){  // Move the pivot value to the right end.
					tmp = target[j]; target[j] = target[mj]; target[mj] = tmp; mj--; }
			if (i > j)  break; 
			// Exchange target[i] and target[j]. 
			tmp = target[i];  target[i] = target[j];  target[j] = tmp; i++; j--;
		}
		// Move the pivot values to the middle.
		for(mi--, i--; left <= mi; mi--, i--){
			tmp = target[i];  target[i] = target[mi];  target[mi] = tmp; }
		for(mj++, j++; mj <= right; mj++, j++){
			tmp = target[j];  target[j] = target[mj];  target[mj] = tmp; }		
		// Sort the left and right arrays.
		ternarySplitQuickSort(target, left, i);
		ternarySplitQuickSort(target, j, right);
	}	

	public static void radixSort(int[] target, int m){ // target != null.	
		// All elements in the array target are assumed to be nonnegative integers.
		int targetLen = target.length;
		// Array for storing a partially sorted list temporarily.
		int[] tmp = new int[targetLen];
		// Array for counting individual numbers in the significant digit.
		int[] count = new int[m];   
		// Compute the maximum and set maxDigit to its number of digits.
		int max = target[0];
		for(int i=1; i<targetLen; i++){ if(max < target[i]) max = target[i]; }
		int maxDigit = 0;
		for(; max > 0; maxDigit++){ max = max/m; }
		// From the least significant digit, sort elements.
		for(int j = 1; j <= maxDigit; j++){  // j denotes the significant gidit.
			// Count the number of elements equal to "i".
			for(int i=0; i<m; i++){ count[i]=0; }
			for(int i = 0; i < targetLen; i++){ count[digit(target[i], j, m)]++; }
			// Count the number of elements less than or equal to "i".
			for(int i=1; i<m; i++){ count[i] = count[i-1] + count[i]; }
			// Scan the input array from the tail, and 
			// insert each element in the proper position in tmp. 
				for(int i = targetLen-1; 0 <= i; i--)
					// Putting -- before count decrements count first.
					tmp[ --count[digit(target[i], j, m)] ] = target[i];	
				for(int i = 0; i < targetLen; i++){ target[i] = tmp[i]; }		
		}
	}		
	public static int digit(int num, int j, int m){
		int quotient = num;
		int remainder = 0;
		for(int i=0; i<j; i++){
			remainder = quotient%m;
			quotient = quotient/m;
		}
		return remainder;
	}

	public static int[] generateRandomNumbers(int targetLen, int max){
		// Generate an array in which elements are selected from {0,1,2,3} at random.
		int[] target = new int[targetLen];
		for(int i=0; i<targetLen; i++) target[i] = (int)Math.floor(Math.random()*max);
		return target;
	}	

	public static int[] generateSortedNumbers(int targetLen){
		int[] target = new int[targetLen];
		for(int i=0; i<targetLen; i++) target[i] = i;
		return target;
	}	
	
	public static int[] copyArray(int[] a){
		int[] answer = new int[a.length];
		for(int i = 0; i < a.length; i++) 
			answer[i] = a[i];
		return answer;
	}
	
	public static void printArray(String message, int[] a){
		System.out.println(message);
		for(int i=0; i<a.length; i++)
			System.out.print(a[i]+" ");
		System.out.println();		
	}
	
	public static void checkAgreement(int[] target0, int[] target1){
		if(target0.length != target1.length)
			System.out.println("\tdisagree");
		else{
			int n = target0.length;
			for(int i=0; i<n; i++){
				if(target0[i] != target1[i]){
					System.out.println("\tdisagree");
					return;
				}
			}
			System.out.println("\tagree");;
		}
	}
	
	public static void main(String[] args) {

		// Test cases.
		int[] a = {48, 195, 12, 49, 198, 24, 99, 140, 48, 195, 12, 48};
//		int[] a = {0, 0, 0, 10, 10, 10};
		
		// Generate a random input.
//		a = generateRandomNumbers(1000000, 1000000); 
//		a = generateSortedNumbers(1000000);
		int[] target0, target;

		Date day;
		long start, end;

		System.out.println("merge sort");		
		target0 = copyArray(a);
		day = new Date(); start = day.getTime();
		mergeSort(target0);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));
/*
		System.out.println("insertion sort");
		target = copyArray(a);
		day = new Date(); start = day.getTime();
		insertionSort(target);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);		
*/
		
		System.out.println("heap sort");		
		target = copyArray(a);
		day = new Date(); start = day.getTime();
		heapSort(target);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));
		checkAgreement(target0, target);
		
		System.out.println("naive random quick sort");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		randomQuickSort1(target);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);		
		
		System.out.println("random quick sort with tail recursion elimination");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		randomQuickSort2(target);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);		
		
		System.out.println("random quick sort with tail recursion elimination and stack depth reduction");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		randomQuickSort3(target);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);		
		
		System.out.println("random quick sort with tail recursion elimination, stack depth reduction, and insertion sort");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		randomQuickSort4(target, 8);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);		
			
		System.out.println("random quick sort with tail recursion elimination, stack depth reduction, and insertion sort at the final step.");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		randomQuickSort5(target, 8);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);				
		
		System.out.println("introspective sort.");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		introspectiveSort(target, 8);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);				

		System.out.println("ternary split quick sort");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		ternarySplitQuickSort(target);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);				
		
		System.out.println("radix sort");
		target = copyArray(a);
		day = new Date(); start = day.getTime();		
		radixSort(target, 1000);
		day = new Date(); end = day.getTime(); System.out.println("\tElapsed time = "+(end-start));		
		checkAgreement(target0, target);			
	}		
	
}