Given that array has $k$ elements (all distributed uniformly).
Its length is exactly $3$ somewhere in $(0, k)$.
For example, if $k=100$ then, we have $100$ numbers and they can be in $(10,13)$, but they can also be at $(89,92)$
I need to offer a sorting algorithm, which is efficient.
Now, my idea was Bucket Sort, but why would I care the length of the interval is $3$ or $1000$ ? if the numbers are distributed uniformly, then it does not even matter because we could do just a “regular” bucket sort!
But there is a solution that instead of linked lists in each bucket, we use AVL trees. Why would that matter?! the elements still distributed so it is $O(1)$ in each AVL-Tree AND $O(1)$ in each linkedlist… I really don’t get it!
Thanks for helping!
