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!