page 3

Code for quick sort
//time: O(NlogN), space: O(1ogN)
private int partition(int[] a, int lo, int hi) {
    int v = a[lo];
    int i = lo;
    int j = hi + 1;
    while(true) {
        while(a[++i] <= v) if(i == hi) break;
        while(a[--j] >= v) if(j == lo) break;
        if(i >= j) break;
        swap(a, i, j);
    }
    swap(a, lo, j);
    return j;
}
private sort(int[] a, int lo, int hi) {
    if(lo >= hi) break;
    int mid = partition(a, lo, hi);
    sort(a, lo, mid - 1);
    sort(a, mid + 1, hi);
}
public sort(int [] a) {sort(a, 0, a.length - 1);}