RadixSort.java

/* Radix sort works on a positive array of numbers,
 * sorting them for each place value in the longest 
 * number in that array.  At each place value, starting from the 
 * right, all numbers in the array are placed into one of 10
 * "buckets" which correspond to each number in the decimal
 * system.  After all numbers are sorted for a value place,
 * the buckets are emptied back into the original array,
 * and the process is repeated for each remaining value place.
 */

import java.util.LinkedList;

public class RadixSort {
    
    /* Perform a radix sort on a set of positive integers
     *
     * @param arr an array of positive integers to be sorted
     * @return the sorted integer array
     */
    public static Integer[] sort(Integer[] arr) {

        // Ensure there are at least two elements in the array
        if (arr == null || arr.length <= 1) return arr;
        
        /* Find the length of the largest element and 
         * ensure there are no negative numbers in the array
         */
        int largest = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > largest) {
                largest = arr[i];
            }
            
            if (arr[i] < 0) {
                throw new IllegalArgumentException();
            }
        }
        
        int longestLength = Integer.toString(largest).length();
        
        /* Create buckets for each digit in the decimal system
         * Each bucket contains a queue which will hold the 
         * array values for that value place
         */
        LinkedList<Integer>[] buckets = new LinkedList[10];
        
        /* Create a divisor variable which will be used to 
         * find the value at a specific value place
         */
        int divisor = 1;
        
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<>();
        }
        
        // Sort the array for each value place in the longest number
        for (int i = 0; i < longestLength; i++) {
            
            // Add each element in the array to the correct bucket
            // for this value place
            for (int j = 0; j < arr.length; j++) {
                buckets[arr[j] / divisor % 10].addLast(arr[j]);
            }
            
            // Empty all the buckets sorted for this value
            // place back into the array
            for (int j = 0, b = 0; j < arr.length; b++) {
                
                // Do all of the items in this bucket
                while (!buckets[b].isEmpty()) {
                    arr[j++] = buckets[b].removeFirst();
                }
            }
            
            // Move to the next value place
            divisor *= 10;
        }
        
        return arr;
    }

    // Test
    public static void main(String[] args) {
        for (Integer s : sort(new Integer[] 
            { 17,333,26,26,0,4111,23240,9 })) {
            System.out.println(s);
        }
    }
}