public class QuickSortInsertion
{
    void quickSortRec(int array[], int left, int right)
    {
    	if(right-left < 100) {
    		InsertionSort s = new InsertionSort();
    		s.insertionSort(array, array.length);
    	} else if(left < right) {
            int pivotIndex = partition(array, left, right);
            quickSortRec(array, left, pivotIndex-1);
            quickSortRec(array, pivotIndex+1, right);
        }
    }
    
    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;
    }

    void quickSort(int array[], int size)
    {
        quickSortRec(array, 0, size-1);
    }

    void swap(int array[], int index1, int index2)
    {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}