public class  quickSort{
//the original version
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]+" ");
		System.out.println();
		if(a.length>0)
        	quick(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
	}
	private static void quick(int[] a, int low, int high) {
        if(low<high){ 
            int middle = getMiddle(a,low,high);
            quick(a, low, middle-1);
            quick(a, middle+1, high);
        }
    }
	private static int getMiddle(int[] a, int low, int high) {
        int temp = a[low];
        while(low<high){
            while(low<high && a[high]>=temp){
                high--;
            }
            a[low] = a[high]; 
            while(low<high && a[low]<=temp){
                low++;
            }
            a[high] = a[low];
        }
        a[low] = temp;
        return low;
    }
}