Quicksort

http://me.dt.in.th/page/Quicksort/

Quicksort 
Time:
O(nlgn) - lgn diving n times, n-1 comparsion, when picking pivot int middle, mid pivot is good
worst O(n^2) - pivot happen to be max/min, breaking down list n time, each with n-1 comparison
Space:
O(lgn) for stack

Tips:
avoid worst case by taking few samples and get median to be pivot

Ex:
   *      last
(low-1)|65138479 2(pivot)//1st: 1 & 6 switch 2nd: wall++
1|(in ex: 0)5638479 2
 pivot - bt
switch 1st ele on the right side of wall and switch with pivot
12|(swap at 1 = wall+1)638479 5(newpivot)


Recusive call:
- find pivot
- left (<pivot) wall right( > pivot)

recuse call reach subarray element that len is 1, sorted because been a pivot

public class quicksort {
    public static int partition(int[] arr, int low, int high){
        int pi = arr[high];
        int wall = low - 1;//wall is the index of last element in current sorted part
        for(int i = low; i <= high - 1; i++){//n-1 comparision            
            if(arr[i] <= pi){//swap
                wall++;
                int tmp = arr[wall];
                arr[wall] = arr[i];
                arr[i] = tmp;
            }
        }   
        //1st element right to wall is new pivot > old one        
        if(arr[wall + 1] > pi){
            wall++;
            arr[high] = arr[wall];
            arr[wall] = pi;
        }
        return wall;
    }
    public static void qsort(int[] arr, int low, int high){
        if(low < high){
            int wall = partition(arr, low, high);//wall is sorted
            //diving n times            
            qsort(arr, low, wall-1);//left subarray that val < pi            
            qsort(arr, wall+1, high);//right subarray that val > pi        
        }
    }
    public static void main(String[] args) {
        int[] arr = {6,5,1,3,8,4,9,2};
        qsort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}