Bucket Sort

Steps:
In bucket sorting technique, we maintain an array(bucket) in which we store the count of that particular indexed element.

Then in the input array, we place the elements from accordingly depending on the number of elements in each bucket.

Code:
import java.util.Arrays;

class BucketSort {
        static public void bucketSort(int[] in, int low, int high) {
                int noOfBucks = high - low + 1;

                int[] buckets = new int[noOfBucks];

                for(int i=0; i<in.length; i++) {
                        int ele = in[i];

                        buckets[ele] = buckets[ele] + 1;
                }

                int insIndex = 0;

                for(int i=0; i<buckets.length; i++) {
                        int eleCount = buckets[i];

                        while(eleCount != 0) {
                                in[insIndex++] = i;
                                --eleCount;
                        }
                }
        }

        static public void main(String[] args) {
                int[] inAr = new int[]{2, 1, 0, 4, 3, 1, 4, 3, 5};

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

                bucketSort(inAr, 0, 5);

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

eg:
Input array: {2, 1, 0, 4, 3, 1, 4, 3, 5}

bucket array: size: 5-0+1 = 6 ==> {1, 2, 1, 2, 2, 5}

Since 0 occurred once in the input array, we keep the count as '1' in the bucket array.
Since 1 occurred twice in the input array, we keep the count as '2' in the bucket array.

Now iterating over the bucket array, we need to keep the numbers equal to its count in the given input array.

Starting from 0th index, keep one 0, since count is 1. Keep the element at index 0.
Now at 1st index, count is 2. So keep two 1's in the input array at indices 1, 2


Complexity Analysis: