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 (hi <= lo) {

return;

}

int lt = lo;

int gt = hi;

int v = charAt(a[lo], d);

int i = lo + 1;

while (i <= gt) {

int t = charAt(a[i], d);

if (t < v) exch(a, lt++, i++);

else if (t > 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);

return -1;

}

private static void exch(String[] a, int x, int y) {

String temp = a[x];

a[x] = a[y];

a[y] = temp;

}

public static void main(String[] args) {

String[] a = {"she", "sells", "seashells", "by", "the", "shore", "the", "seashells", "are", "shellish", "and", "made", "from", "shellfish"};

for (String s : a)

System.out.print(s + " ");

System.out.println();

sort(a);

for (String s : a)

System.out.print(s + " ");

System.out.println();

}