import java.util.LinkedList;

public class BucketSort {
    public static void main(String[] args) {
	
	int[] numbers = {34,56,32,123,45,54,76,63,7,321,432,67,8,321,456,234,5,432,3,21,43,2};
	
	int[] output = bucketSort(numbers, 10);
	
	for(int i = 0; i < output.length; i++)
	    System.out.print(output[i] + " ");
    } 
    
    /**
     * Sort using a Bucket Sort Algorithm 
     */
    public static int[] bucketSort(int[] toSort, int N) {
	LinkedList[] buckets = new LinkedList[N];

	// Initialize the Empty buckets
	for(int i = 0; i < N; i++) {
	    buckets[i] = new LinkedList();
	}
	
	int len = toSort.length;
	int max = 0;
	for(int i = 0; i < len; i++) 
	    if(toSort[i] > max) 
		max = toSort[i];

	//if (max == 0) return null;
	System.out.println("Max " + max);
	int hashValue = max / N;
	
	System.out.println("Len " + len);
	System.out.println("Hash " + hashValue);
	
	for(int i = 0; i < len; i++) {
	    int key;
	    
	    if (hashValue == 0) { 
		key = 0;
	    } else {
		key = toSort[i] / hashValue;
	    }
	    //System.out.println("Len " + len + " I " + i + " Sort Num: " + toSort[i] + " key: " + key);
	    if (key >= N) key = N - 1;
	    buckets[key].add(new Integer(toSort[i]));
	    //buckets[0].add(new Integer(0));//toSort[0]));
	}
	
	int[] sortedArray = new int[len];
	int spot = 0;
	for(int i = 0; i < N; i++) {
	    //System.out.println("I: " + i + " buckets.length " + buckets.length);
	    Object[] tmpCurrentBucket = buckets[i].toArray();
	    int[] currentBucket = new int[tmpCurrentBucket.length];
	    for(int j = 0; j < currentBucket.length; j++){
		//System.out.println("J " + j);
		currentBucket[j] = ((Integer)tmpCurrentBucket[j]).intValue();
	    
		//if (N > 1) N = N / 2;
		if(currentBucket.length > 2) 
		    currentBucket = bucketSort(currentBucket, N);
		for(int k = 0; j < currentBucket.length; k++) {
		    sortedArray[spot++] = currentBucket[k];
		}
	    }
	}
	
	
	return sortedArray;
    }
}