Is there a way to skip empty buckets during bucket sort?

One option would be to hold an auxilary BST containing which buckets are actually being used. Whenever you add something to a bucket, if it's the first entry to be placed there, you would also add that bucket's value to the BST.

One option would be to hold an auxilary BST containing which buckets are actually being used. Whenever you add something to a bucket, if it's the first entry to be placed there, you would also add that bucket's value to the BST. When you want to then go concatenate everything, you could then just iterate over the BST in sorted order, concatenating just the buckets you find.

If there are z buckets that actually get used, this takes O(n + z log z). If the number of buckets is large compared to the number actually used, this could be much faster. More generally - if you have a way of sorting the z different buckets being used in O(f(z)) time, you can do a bucket sort in O(n + f(z)) time.

Maintain a second array of the buckets you actually use, adding a bucket to the array when it's used for the first time. Before iterating over the buckets, sort in O(f(z)) time the indices of the buckets in usem then iterate across that array to determine what buckets to visit. For example, if you used y-Fast trees, you could sort in O(n + z log log z).

Hope this helps!

This wouldnt help 1 reason is if the Bucket sort dealing with a good distrabution of elements in A, which leads to an Ele or Constant of Eles in a bucket would lead us to O(n/c*logn/c) which is O(nlogn) - rather use QuickSort in this case. – Ofek Ron Aug 31 at 22:47 1 @Ofek: But you said that n – Oli Charlesworth Aug 31 at 22:49 in some way you are right, but its actually still is not so helpfull since we don't want to assume too much strict rules on the input i. E the distrabution of the input, the input could be with no 2 equal keys and then what?

We get to do the buckets partition for dealing with exactly the same problem again - sorting the very same array – Ofek Ron Aug 31 at 22:54 Can you explain a lil about y-Fast? – Ofek Ron Aug 31 at 23:30 @Ofek Ron- You should probably check out the Wikipedia article for van Emde Boas trees, x-Fast trees, and then y-Fast trees to get a sense for how these structures work. They're definitely not trivial, but it might be good to know about them if you want to do fast integer sorts.

– templatetypedef Aug 317 at 0:28.

You can turn the bucket array into an associative array, which yields O(n log n), and I don't believe you can do better than that for sorting (on average). O(n) is impossible in the general case.

But doesn't the same problem exist for an associative array when the number of bins vastly exceeds the number of elements> – Oli Charlesworth Aug 31 at 22:48 @Oli: Yes. I've amended my answer to clarify my stance. – Marcelo Cantos Sep 1 at 7:54.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.