Bucket sort works well with relatively small, known key values. It also works well when there are just a few elements per bucket, on average. The ideal result is when the contents of the buckets are trivial. One example of this is when there is only one key held by each bucket.(1)
Another way to look at it is this: bin sort works very well when the keys of the objects to be sorted lie in a small range and there is only one item with each value of the key. When these two constraints are met, bucket sort is an O(n) algorithm. However, this is only true when these constraints are met. Otherwise, heap sort and quick sort are usually preferable.(4)
Bucket sort has a worst case of O(n log log n).(1)
