@Override
    public void sort(int[] array) {
        if (bucketCount <= 0) {
            throw new IllegalArgumentException("Invalid bucket count");
        }
        if (array.length <= 1) {
            return;
        }
        int high = array[0];
        int low = array[0];
        for (int i = 1; i < array.length; i++) { //find the range of input elements
            if (array[i] > high) {
                high = array[i];
            }
            if (array[i] < low) {
                low = array[i];
            }
        }
        double interval = ((double) (high - low + 1)) / bucketCount; //range of one bucket
        ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) { //initialize buckets
            buckets[i] = new ArrayList();
        }
        
        for (int i = 0; i < array.length; i++) { //partition the input array
            int index = (int) ((array[i] - low) / interval);
            buckets[index].add(array[i]);
        }

        int idx = 0;
        for (int i = 0; i < buckets.length; i++) {
            Collections.sort(buckets[i]); //mergeSort            
            for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
                array[idx++] = buckets[i].get(j);
            }            
        }
        
        
    }