QUICK-SORT

Input: A(p, r)

QUICK-SORT(A, p, r){
if (p < r){
q = PARTITION(A, p, r);
QUICK-SORT(A, p, q-1);
QUICK-SORT(A, q+1, r);
}
}

Subroutine:
PARTITION(A, p, r){
i = p -1;
x = A[r];
for (j = p; j <= r-1; j++){
if (A[j] <= x){
i++;
exchange(A[i], A[j]);
}
}
exchange(A[i+1], A[r]);
return i+1;
}

Features:
1. T(n) = O(nlgn) ~ O(n2)
2. Sort in place