Radix Sort

Steps:
This algorithm depends on the number of digits present in a given number.
First it sorts the number based on the last digit of each number.
Then it sorts the above result based on the second last digit of each number.
This will be continued till the first digit of the number.

At the end array will be sorted.

Code:
import java.util.Arrays;

class RadixSort {
        static public void radixSort(int[] in, int numOfDigs) {
                int[][] buckets = new int[10][in.length];

                int numToDiv = 10;

                for(int i=numOfDigs; i>0; i--) {
                        for(int j=0; j<in.length; j++) {
                                int lastDigit = in[j] % numToDiv;

                                if(numToDiv > 10)
                                        lastDigit = lastDigit/(numToDiv/10);

                                int pos = 0;
                                while(buckets[lastDigit][pos] != 0)
                                        ++pos;

                                buckets[lastDigit][pos] = in[j];
                        }

                        int insIndex = 0;

                        for(int j=0; j<buckets.length; j++) {
                                //take out all elements from buckets
                                //keep then in the input array
                                //empty the bucket arrays
                                int[] bucketAr = buckets[j];

                                for(int k=0; k<in.length; k++) {
                                        if(bucketAr[k] != 0)
                                                in[insIndex++] = bucketAr[k];
                                        else
                                                break;
                                }

                                buckets[j] = new int[in.length];
                        }

                        numToDiv = numToDiv*10;
                }
        }

        static public void main(String[] args) {
                int[] in = {321, 213, 320, 111, 435, 398};

                System.out.println(Arrays.toString(in));

                radixSort(in, 3);

                System.out.println(Arrays.toString(in));
        }
}

eg:
{321, 213, 320, 111, 435, 398}
Here we are maintaining the sorted elements in the digit buckets each time, then we are moving them back to original array.
Since there can be 10 possible digits in a decimal system, we maintain 10 buckets to store each digits numbers.

1st iteration:
since last digit of 321 is "1", keep 321 in the 2nd bucket(1st index)
since last digit of 213 is "3", keep 213 in the 4th bucket(3rd index)
...
Now the buckets are:
0 --> {320}, 1--> {321, 111}, 2 --> {}, 3 --> {213}, 4 --> {}, 5 --> {435}, 6 --> {}, 7 --> {}, 8 --> 398}

Now starting from 0th bucket, retrieve all the elements in the order of insertion in each bucket and keep them back in the original array.
So the original array will now become: {320, 321, 111, 213, 435, 398}
Here you can observe that the array is now sorted by last digit.

Now based on this array, sort it again wrt second digit, which gives:
{111, 213, 320, 321, 435, 398}

Last, sort it based on first digit:
==> {111, 213, 320, 321, 398, 435}


Complexity Analysis: