package main
import "fmt"
 
type ElemType int;
 
func main() {
    data := make([]ElemType, 600000) // ALL ZERO
    var i int = 0;
    var dlen int = len(data);
    for i = 0 ; i < dlen ; i++{
        data[i] = (ElemType)(dlen - i -1);
    }
    fmt.Println("Start ...",len(data));
    for i = 0 ; i < 100 ; i++{
        fmt.Printf("%d ", data[i]);
    }
    fmt.Println();
    QuickSort(data,0,dlen-1);
    
    fmt.Println("End ...");
    for i = 0 ; i < 100 ; i++{
        fmt.Printf("%d ", data[i]);
    }
    fmt.Println();
}
 
func QuickSort(A []ElemType,low, high int){
    if low < high {
        // Partition() is the operation of divide A[low ... high]
        // one to two arrays which can be used as QuickSort Again
        pivotpos := Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}
 
func Partition(A []ElemType,low ,high int)  int {
    var pivot ElemType = A[low];
    var tmp ElemType;
    //Method I:
    //for low < high {
    //  for low < high && A[high] >= pivot { high-- ; }
    //  A[low] = A[high];
    //  for low < high && A[low] < pivot { low++; }
    //  A[high] = A[low];
    //}
    //end of MI
    
    //Method II:
    for (low < high) && (A[high] > pivot) { high --; }
    for (low < high) && (A[low] < pivot) {low++; }
    for low < high {
        // swap A[low] & A[high]
        tmp = A[low];
        A[low] = A[high];
        A[high] = tmp;
        low ++;
        high --;
    }
    //end of MII
 
    A[low] = pivot ;
    return low ;
}