Bucket Sort in Java with Example

In recent years, one of the question I have increasingly seen in programming job interviews is about constant time sorting algorithms e.g. do you know any O(n) sorting algorithm? When I first encountered this question, I had no idea whether we can sort in constant time because even some of the fastest sorting algorithms e.g. QuickSort or MergeSort takes O(N log N) time for sorting. After some research, I come to know that there are some constant time algorithms e.g. bucket sort, counting sort and radix sort, which can sort an array in O(n) time. The idea of bucket sort is quite simple, you distributes the elements of an array into a number of buckets and then sort those individual bucket by a differnet sorting algorithm or by recursively applying the bucket sorting algorithm.

Read more �