public class QuickSortInsertion
{
    public void quickSortInsertion(int array[])
    {
    	
        quickSortRec(array, 0, array.length-1);
        insertSortIter(array, left, right);
    }
    
    private void quickSortRec(int array[], int left, int right)
    {
    	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;
    }
    
    // Sort parts of a vector
    private void insertSortIter(int[] array, int left, int right)
    {
    	if(right-left < 30) {
    		for(int i=left; i<=right; i++) {
    			insert(array, i, array[i]);
    		}
    	}
    }
    
    private void insert(int[] array, int left, int right) {
    	int i = left;
    	int value = array[left];
        while (i <= right && array[i] > value) {
            array[i+1] = array[i];
            i--;
        }
        array[i+1] = value;
    }
    
    private void swap(int array[], int index1, int index2)
    {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}