public class QuickSortInsertion
{
    public void quickSortInsertion(int array[])
    {
        quickSortRec(array, 0, array.length-1);
    }
    
    private void quickSortRec(int array[], int left, int right)
    {
    	if(right-left < 10) {
    		insertionSort(array, left, right);
    	} else {
    		int pivotIndex = partition(array, left, right);
    		quickSortRec(array, left, pivotIndex-1);
    		quickSortRec(array, pivotIndex+1, right);
    	}
    }
    
    private int partition(int array[], int left, int right)
    {
    	int pivot = array[left];
        int limit = left;
        for (int i=left+1; i <= right; i++) {
            if (array[i] < pivot) {
                limit++;
                swap(array, limit, i);
            }
        }
        swap(array, left, limit);
        return limit;
    }
    
    private void insert(int[] a, int left, int right, int value) { 
        int i = right-1;
        while (i >= left && a[i] > value) {
        	a[i+1] = a[i];
        	i--; 
        } 
        a[i+1] = value; 
    } 
     
    public void insertionSort(int[] a, int left, int right) { 
        int i = left; 
        while (i < right) { 
        	System.out.println(i);
            insert(a, i, right, a[i]); 
            i++; 
        } 
    }
    
    private void swap(int array[], int index1, int index2)
    {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}