# algorithms – Sorting an interval

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!