//time: N to Nw, space: W + logN
public class Quick3String {
public static void sort(String[] a) {
sort(a, 0, a.length - 1, 0);
}
private static void sort(String[] a, int lo, int hi, int d) {
if(lo >= hi) return;
int lt = lo;
int gt = hi;
int i = lo + 1;
int v = charAt(a[lo], d);
while(i <= gt) {
int x = charAt(a[i], d);
if(x < v) exch(a, i++, lt++);
else if(x > v) exch(a, i, gt--);
else i++;
}
sort(a, lo, lt - 1, d);
if(v >= 0) sort(a, lt, gt, d + 1);
sort(a, gt + 1, hi, d);
}
private static int charAt(String s, int d) {
if(d < s.length()) return s.charAt(d);
else return -1;
}
private static void exch(String[] a, int i, int j) {
String t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String...args) {
String[] a = new String[]{"apple", "orange", "apple", "add", "application", "aptitude", "eggplant", "egg"};
sort(a);
for(String s : a) {
System.out.println(s);
}
}
}
