package quickSort;

public class QuickSort {
	private static <T extends Comparable<? super T>> void sortFirstMiddleLast(T[] a,int first ,int mid ,int last)
	{
		order(a,first,mid);
		order(a,mid,last);
		order(a,first,mid);
	}
	
	private static <T extends Comparable<? super T>> void order(T[] a,int i,int j)
	{
		if(a[i].compareTo(a[j])>0)
		{
			swap(a,i,j);
		}
	}
	
	private static void swap(Object[] array,int i,int j)
	{
		Object temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	private static <T extends Comparable<? super T>> int partition(T[] a,int first,int last)
	{
		int mid = (first+last)/2;
		sortFirstMiddleLast(a,first,mid,last);
		
		swap(a,mid,last-1);
		int pivotIndex = last-1;
		T pivot = a[pivotIndex];
		
		int indexFromLeft = first +1;
		int indexFromRight = last - 2;
		
		boolean done = false;
		while(!done)
		{
			while(a[indexFromLeft].compareTo(pivot) <0)
				indexFromLeft++;
			
			while(a[indexFromRight].compareTo(pivot) >0)
				indexFromRight--;
			
			assert a[indexFromLeft].compareTo(pivot) >= 0 && a[indexFromRight].compareTo(pivot) <=0;
			
			if(indexFromLeft < indexFromRight)
			{
				swap(a,indexFromLeft,indexFromRight);
				indexFromLeft++;
				indexFromRight--;
			}else{
				done = true;
			}
		}
		
		return pivotIndex;
	}
}