Test.java

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        int[] arr = new int[50];
        for(int i = 0; i < arr.length; ++i) {
            arr[i] = (int)(Math.random()*1024);
        }
        bucket_sort(arr);
        for(int i : arr) {
            System.out.println(i);
        }
    }
    public static void bucket_sort(int[] arr) {
        boolean allEqual = true;
        for(int i = 0; i < arr.length-1; ++i)
            if(arr[i] != arr[i+1])
                allEqual = false;
        if(allEqual)
            return;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < 32; ++i) {
            buckets.add(new ArrayList<Integer>());
        }
        for(int a : arr) {
            if(a == 0)
                buckets.get(0).add(a);
            else
                buckets.get((int)((Math.log(a))/(Math.log(2)))+1).add(a);
        }
        for(int i = 0; i < buckets.size(); ++i) {
            int[] dummy = new int[buckets.get(i).size()];
            int d = 0;
            for(int j : buckets.get(i))
                dummy[d++] = j-((int)(Math.pow(2,i-1)));
            bucket_sort(dummy);
            for(d=0; d<dummy.length;d++)
                buckets.get(i).set(d,dummy[d]+((int)Math.pow(2,i-1)));
        }
        int r = 0;
        for(int i = 0; i < buckets.size(); ++i) {
            for(int j = 0; j < buckets.get(i).size(); ++j) {
                arr[r++] = buckets.get(i).get(j);
            }
        }
    }
}