# 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!

You can use a counting sort: if the first element of the array is $$n$$, then the values of the array are between $$n-2$$ and $$n+2$$. If you count the number of elements equal to each of these 5 values and reorder them, your data are sorted.

This can be done because numbers are in an interval of length 3, so you only have 5 different values to consider given the first one.

You don't need any fancy data structures at all, using counting sort.

Initialize three-element array $$C$$ to all $$0$$s and $$x$$ to infinity. Then loop over every element in $$A[i]$$ and:

1. Increment $$C[A[i] \bmod 3]$$.
2. If $$A[i] < x$$ set $$x = A[i]$$.

Finally, output an array consisting of $$x$$ repeated $$C[x \bmod 3]$$ times, followed by $$x + 1$$ repeated $$C[(x+1)\bmod 3]$$ times and finally $$x + 2$$ repeated $$C[(x+2)\bmod 3]$$ times.

• But, why is the solution I wrote, your soution and Nathaniel's are the most optimized? I mean, one of them is the most efficient no? So how would I know how to answer here? In a simple analysis all three seem $O(n)$ which is really the same (both runtime and space I believe) Feb 21, 2021 at 4:08
• (Excruciatingly data space conscious;) Feb 21, 2021 at 7:56