//time: Nlog(N), space: logN
public class Quick3Way {
static void sort(int[] a) {
sort(a, 0, a.length - 1);
}
static void sort(int[] a, int lo, int hi) {
if(lo >= hi) return;
int lt = lo;
int gt = hi;
int v = a[lo];
int i = lo + 1;
while(i <= gt) {
if(a[i] < v) exch(a, lt++, i++);
else if(a[i] > v) exch(a, i, gt--);
else i++;
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
static void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String...args) {
int[] a = new int[] {3, 6, 0, 9, 2, 3, 1, 0, 7, 2, 3, 9};
Quick3Way.sort(a);
for(int i : a) {
System.out.println(i);
}
}
}
