Bucket sort for integers

Could anybody help me with the bucket sort algorithm for integers? Often people mistakenly say they have this algorithm, but actually have a counting sort! Maybe it works similarly, but it is something different.

I hope you will help me find the right way, because now I have no idea (Cormen's book and Wikipedia are not so helpful).

Thanks in advance for 开发者_StackOverflowall your respones.

Bucket sort can be seen as a generalization of counting sort; in fact, if each bucket has size 1 then bucket sort degenerates to counting sort.

Counting sort will only work on integers, while bucket sort can work on anything with a value, also, the final loop is a bit different.

Counting Sort maintains an additional array of ints, which basically counts how many of a certain number there is, and then creates the number again when it goes through the additional array in the final loop, what I mean by this is - in a OOP way of looking at it, it's not the same object, but a new object with identical value.

Then, we have bucket sort. Bucket sort goes through the array, but instead of just going ++ in the relevant place in the array, it inserts the item into a list of some kind (I like to use a queue, that way it's a stable sort). Then, in the final loop, the algorithm goes through the entire additional array, and dequeues the elements in each bucket into the array. That way it's the same object.

If you're sorting anything and you know that the range of numbers is smaller then nlogn, it's simple - use counting sort if it's integers, and bucket sort if the object has some additional data. You can use bucket sort for integers, sure, but counting sort will take much less space.