MSD.java

package string;

public class MSD {
    private static String[] aux;
    private static final int R = 26;

    private static void sort(String[] a) {
        aux = new String[a.length];
        sort(a, aux, 0, a.length - 1, 0);
    }

    private static void sort(String[] a, String[] aux, int lo, int hi, int d) {
        if (hi <= lo) return;
        
        int[] count = new int[R + 2];

        for (int i = lo; i <= hi; i++) 
            count[charAt(a[i], d) + 2]++;
        for (int r = 0; r < R + 1; r++)
            count[r + 1] += count[r];
        for (int i = lo; i <= hi; i++) 
            aux[count[charAt(a[i], d) + 1]++] = a[i];
        for (int i = lo; i <= hi; i++)
            a[i] = aux[i - lo];

        for (int r = 0; r < R; r++) 
            sort(a, aux, lo + count[r], lo + count[r + 1] - 1, d + 1);
    }

    private static int charAt(String s, int d) {
        if (d < s.length()) return s.charAt(d) - 'a';
        return -1;
    }

    public static void main(String[] args) {
        String[] a = {"cat", "mat", "dog", "hat", "dom", "don", "rat", "vat", "run", "cut", "pot", "lot", "put", "rub", "tub", "sub", "dub", "jug", "rug", "mug", "bug", "yak"};
        int N = a.length;
        for (int i = 0; i < N; i++)
            System.out.print(a[i] + " ");
        System.out.println();
        sort(a);
        for (int i = 0; i < N; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}