public class pivot{
    final static int CUTOFF = 10;
    
    public static void main(String[] args){
        int[] numbers = {18,100,84,75,95,54,55,30};
        quickSort(numbers);
        for(int element:numbers){
            System.out.println(element);
        }
    }
    private static void quickSort(int[] a){
        
        quickSort(a,0,a.length-1);
    }
    private static void quickSort(int[] a, int lo, int hi){
        if(lo + CUTOFF > hi){
            insertionSort(a,lo,hi);
        }else{
            int mi = (lo+hi)/2;
            if(a[mi]<a[lo]) swap(a,lo,mi);
            if(a[hi]<a[lo]) swap(a,lo,hi);
            if(a[hi]<a[mi]) swap(a,mi,hi);
            
            swap(a,mi,hi-1);
            int p = a[hi-1];
            
            int i,j;
            
            for(i=lo,j=hi-1; ; ){
                while(a[++i]<p);
                while(p<a[--j]);
                if(i<j) swap(a,i,j);
                else break;
            }
            
            swap(a,i,hi-1);
            quickSort(a,lo,i-1);
            quickSort(a,i+1,hi);
        }
    }
    private static void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
    private static void insertionSort(int[] a,int lo,int hi){
        if(lo>hi||lo<0||hi>=a.length){
            lo = 0;
            hi = a.length-1;
        }
        for(int i=lo+1;i<=hi;i++){
            int tmp = a[i];
            int k = i-1;
            while(k>=lo&&tmp<a[k]){
                a[k+1]=a[k];
                k--;
            }
            a[k+1]=tmp;
        }
    }
}