public class RadixSort { 
    public static int max(int arr[]) {
        int M = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > M) {
                M = arr[i];
            }
        }
        return M;
    }

    public static int maxdigits(int max) {
        int count = 0;
        while (max !=0) {
            max = max / 10;
            count++;
        }
        return count;
    }

    public static void print(int a[]){
        for (int j = 0; j < a.length; j++){
            System.out.print (a[j] + "  " );
        }
        System.out.println("\n");
    }

    public static void main(String args[]) {
        System.out.println("Radix Sort");
        int a[] = {31, 41, 59, 26, 53, 58, 97, 93, 23, 84};
        int pass = 0;
        int counts[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int offset[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int answer[] =new int[a.length];
        int k = maxdigits(max(a));
        System.out.println ("Max = " + max(a) + " k = " + k);
        int count = 0;
        print(a);
        for (int i = 1; i <=k; i++){
            System.out.println ("Pass#" + i + ":");
            for (int j = 0; j < a.length; j++){
                int digit = a[j]/((int) Math.pow(10, i-1));
                int value = digit % 10;
                counts[value]++;
                count++;
            }
            for (int j = 1; j < offset.length; j++){
                int sum = 0;
                for (int p = 0; p < j; p++){
                    sum += counts[p];
                    count++;
                }
                offset[j] = sum;
                count++;
            }
            System.out.print ("Counts array : " );
            print(counts);
            for (int j = 0; j < a.length; j++){
                int digit = a[j]/((int) Math.pow(10, i-1));
                int value = digit % 10;
                int cell = offset[value];
                answer[cell] = a[j];
                offset[value]++;
                count++;
            }
            System.out.print ("Offsets array : " );
            print(offset);
            for (int j = 0; j < a.length; j++){
                a[j] = answer[j];
                answer[j] = 0;
                count++;
            }
            for (int j = 0; j < counts.length; j++){
                counts[j] = 0;
                offset[j] = 0;
                count++;
            }
            print(a);
        }
    }
}