// Stably sort an array of chars using key-indexed counting sort.
// Pulled this out of the inner loop of ../book/LSD.java

public class CharSort
{
    // We assume all chars in extended ASCII range.
    static int R = 256;

    // Sort from input to output
    static void sort(char[] input, char[] output)
    {
        int N = input.length;
        // compute frequency counts
        int[] count = new int[R+1];
        for (int i = 0; i < N; i++)
            count[input[i] + 1]++;
        // compute cumulates
        for (int r = 0; r < R; r++)
            count[r+1] += count[r];
        // move data
        for (int i = 0; i < N; i++)
            output[count[input[i]]++] = input[i];
        // no copy back
    }

    public static void main(String[] args)
    {
        char[] L = {'a', 'n', 'n', 'b', '%', 'a', 'a'};
        char[] F = new char[L.length];
        System.out.print("input:  ");
        System.out.println(L);
        sort(L, F);
        System.out.print("output: ");
        System.out.println(F);
    }
}