import java.lang.*;

public class QSortInsertion
{
    private int[] resArray;

    public QSortInsertion(int array[])
    {
        quickSortRec(array, 0, (int)array.length-1);
    }

    private void quickSortRec(int array[], int left, int right)
    {
        int[] resArray = new int[array.length+1]; //new
        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 insertionSort(int[] array, int left, int right)
    {
        boolean bNeedSwapCheck=false;
        for(int i=0; ((i<right) && (bNeedSwapCheck=true)); i++) {
            if( array[i] > array[i+1] ){
               swap(array, i, i + 1);
               bNeedSwapCheck=true;
               System.out.println("need swap i=" + i);
               i=left;
            }
            else
               bNeedSwapCheck=false;
        }
    }

    /*private void insert(int[] array, int left, int right, int value) {
        int i = left;

        System.out.println("before i="+i+ " left=" +left+ " right=" + right + " array[i]=" +array[i] + " value=" +value);

         while (i <= right && array[i] <= value) { //changed
            System.out.println("i="+i+" right=" + right + " array[i]=" +array[i] + " value=" +value);

            resArray[i] = array[i];  //changed
            i++;
        }
        resArray[i+1] = value; //changed
    }*/
    private void swap(int array[], int index1, int index2)
    {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void main(String[] args){
       int qsi[] = new int[] {5,3,7,8,5,3,0};
       QSortInsertion qs = new QSortInsertion(qsi);
       System.out.println("start");
       for(int i=0;i<qsi.length;i++){
           System.out.println(qsi[i]);
       }
       System.out.println("finish");
    }

}