import java.util.Comparator;

public class Sorts {
	private Comparator theComparator;
	
	public Sorts() {
		theComparator = new NaturalComparator();
	} // end constructor
	
	public Sorts(Comparator c) {
		theComparator = c;
	} // end constructor
		

	public static void insertionSort(int[] A) {
		insertionSort(A,0,A.length-1);
	} // end insertionSort

	private static void insertionSort(int[] A, int left, int right) {
		for( int i = left+1; i <= right; i++ ) {
			int hold = A[i];
			int j;
			for( j = i-1; j >= 0 && A[j] > hold; j-- ) {
				A[j+1] = A[j];
			} // end for
			A[j+1] = hold;
		} // end for
    } // end insertionSort

	public void insertionSort(Object[] A) {
		insertionSort(A,0,A.length-1);
	} // end insertionSort

	private void insertionSort(Object[] A, int left, int right) {
		for( int i = left+1; i <= right; i++ ) {
			Object hold = A[i];
			int j;
			for( j = i-1; j >= 0 && theComparator.compare(A[j],hold) > 0; j-- ) {
				A[j+1] = A[j];
			} // end for
			A[j+1] = hold;
		} // end for
    } // end insertionSort

	public static void shellSort(int[] A) {
		for( int gap = A.length/2; gap > 0; gap = gap==2 ? 1 : (int)(gap/2.2)) {
			for( int i = gap; i < A.length; i++ ) {
				int hold = A[i];
				int j;
				for( j = i; j >= gap && hold < A[j-gap]; j -= gap){
					A[j] = A[j-gap];
				}
				A[j] = hold;
			}
		}
	}

	public void shellSort(Object[] A) {
		for( int gap = A.length/2; gap > 0; gap = gap==2 ? 1 : (int)(gap/2.2)) {
			for( int i = gap; i < A.length; i++ ) {
				Object hold = A[i];
				int j;
				for( j = i; j >= gap && theComparator.compare(hold,A[j-gap]) < 0; j -= gap){
					A[j] = A[j-gap];
				}
				A[j] = hold;
			}
		}
	}

	private static int minChild(int[] A, int last, int n) {
		int min = 2*n;
		if( min == last ) return min; // no right child
		if( A[min] < A[2*n + 1] ) {
			min = 2*n + 1;
		}
		return min;
	} // end minChild

	private static void pushDown(int[] A, int last, int n) {
		int hold = A[n];
		while(true) {
		if( 2*n > last ) break; // heap is OK
			int minChild = minChild(A,last,n);
		if( hold >= A[minChild] ) break; // heap is OK
			A[n] = A[minChild];
			n = minChild;
		} // end while
		A[n] = hold;
	} // end pushDown

	private static void heapify(int[] A, int last) {
		for( int i = last/2; i >= 0; i-- ) {
			pushDown(A,last,i);
		}
	} // end heapify

	public static void heapSort(int[] A) {
		int size = A.length;
		heapify(A,size-1);
		for( int i = size; i > 0; i-- ) {
			int hold = A[0];
			A[0] = A[size-1];
			A[size-1] = hold;
			size--;
			pushDown(A,size-1,0);
		}
	} // end heapSort

 	private int minChild(Object[] A, int last, int n) {
		int min = 2*n;
		if( min == last ) return min; // no right child
		if( theComparator.compare(A[min],A[2*n + 1]) < 0 ) {
			min = 2*n + 1;
		}
		return min;
	}

	private void pushDown(Object[] A, int last, int n) {
		Object hold = A[n];
		while(true) {
		if( 2*n > last ) break; // heap is OK
			int minChild = minChild(A,last,n);
		if( theComparator.compare(hold,A[minChild]) >= 0 ) break; // heap is OK
			A[n] = A[minChild];
			n = minChild;
		} // end while
		A[n] = hold;
	}

	private void heapify(Object[] A, int last) {
		for( int i = last/2; i >= 0; i-- ) {
			pushDown(A,last,i);
		}
	} // end heapify

	public void heapSort(Object[] A) {
		int size = A.length;
		heapify(A,size-1);
		for( int i = size; i > 0; i-- ) {
			Object hold = A[0];
			A[0] = A[size-1];
			A[size-1] = hold;
			size--;
			pushDown(A,size-1,0);
		}
	} // end heapSort
	
	public static void mergeSort(int[] a) {
		mergeSort(a,0,a.length-1);
	} // end mergeSort
	
	private static void mergeSort(int[] a, int left, int right) {
		if( left >= right ) return;
		int middle = (left + right) / 2;
		mergeSort(a,left,middle);
		mergeSort(a,middle+1,right);
		int[] b = new int[right-left+1];
		int l = left;
		int r = middle + 1;
		int i = 0;
		while( l <= middle && r <= right) {
			if( a[l] <= a[r] ) {
				b[i++] = a[l++];
			} else {
				b[i++] = a[r++];
			} // end if/else
		} // end while
		while( l <= middle ) b[i++] = a[l++];
		while( r <= right ) b[i++] = a[r++];
		i = left;
		for( int j = 0; j < b.length; j++ ) a[i++] = b[j];
	} // end mergeSort				
	
	public static void mergeSort(Object[] a) {
		mergeSort(a,0,a.length-1);
	} // end mergeSort
	
	private static void mergeSort(Object[] a, int left, int right) {
		if( left >= right ) return;
		int middle = (left + right) / 2;
		mergeSort(a,left,middle);
		mergeSort(a,middle+1,right);
		Object[] b = new Object[right-left+1];
		int l = left;
		int r = middle + 1;
		int i = 0;
		while( l <= middle && r <= right) {
			if( ((Comparable)a[l]).compareTo(a[r]) <= 0 ) {
				b[i++] = a[l++];
			} else {
				b[i++] = a[r++];
			} // end if/else
		} // end while
		while( l <= middle ) b[i++] = a[l++];
		while( r <= right ) b[i++] = a[r++];
		i = left;
		for( int j = 0; j < b.length; j++ ) a[i++] = b[j];
	} // end mergeSort				
	

	public static void quickSort(int[] a) {
		quickSort(a,0,a.length-1);
	}

	private static void quickSort(int[] A, int left, int right) {
		if( left + 10 > right )
			insertionSort(A, left, right);
		else {
			int middle = (left + right) / 2;
			if( A[middle] < A[left] ) {
				int temp = A[middle];
				A[middle] = A[left];
				A[left] = temp;
			}
			if( A[right] < A[left] ) {
				int temp = A[right];
				A[right] = A[left];
				A[left] = temp;
			}
			if( A[right] < A[middle] ) {
				int temp = A[middle];
				A[middle] = A[right];
				A[right] = temp;
			}
			int temp = A[middle];
			A[middle] = A[right-1];
			A[right-1] = temp;
			int pivot = A[right-1];
			int i,j;
			for( i = left, j = right-1; ; ) {
				while( A[++i] < pivot );
				while( pivot < A[--j] );
			if( i >= j ) break;
				temp = A[i];
				A[i] = A[j];
				A[j] = temp;
			}
			temp = A[i];
			A[i] = A[right-1];
			A[right-1] = temp;

			quickSort(A, left, i-1);
			quickSort(A, i+1, right);
		} // end else
	} // end quickSort

	public void quickSort(Object [] A) {
		quickSort(A,0,A.length-1);
	}

	private void quickSort(Object[] A, int left, int right) {
		if( left + 10 > right )
			insertionSort(A, left, right);
		else {
			int middle = (left + right) / 2;
			if( theComparator.compare(A[middle],A[left]) < 0 ) {
				Object temp = A[middle];
				A[middle] = A[left];
				A[left] = temp;
			}
			if( theComparator.compare(A[right],A[left]) < 0 ) {
				Object temp = A[right];
				A[right] = A[left];
				A[left] = temp;
			}
			if( theComparator.compare(A[right],A[middle]) < 0 ) {
				Object temp = A[middle];
				A[middle] = A[right];
				A[right] = temp;
			}
			Object temp = A[middle];
			A[middle] = A[right-1];
			A[right-1] = temp;
			Object pivot = A[right-1];
			int i,j;
			for( i = left, j = right-1; ; ) {
				while( theComparator.compare(A[++i],pivot) < 0 );
				while( theComparator.compare(pivot,A[--j]) < 0 );
			if( i >= j ) break;
				temp = A[i];
				A[i] = A[j];
				A[j] = temp;
			}
			temp = A[i];
			A[i] = A[right-1];
			A[right-1] = temp;

			quickSort(A, left, i-1);
			quickSort(A, i+1, right);
		} // end else
	} // end quickSort

	private class NaturalComparator implements Comparator {
		public int compare(Object A, Object B) {
			return ((Comparable)A).compareTo(B);
		} // end compare
	} // end NaturalComparator			

} // end Sorts