Let $A$ be an array of n elements. We know that $n - \lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$ (the other $\lfloor \sqrt n \rfloor$ elements may or may not be in the range). I need to sort the array in $\Theta (n)$.
I thought of partitioning the array to 3 subarray:
- elements smaller than $\sqrt n$
- element in range $\sqrt n$ to $n\sqrt n$
- element bigger than $n\sqrt n$
the first and last subarrays can be sorted with insertion sort in $O(n)$ because there are at most $\lfloor \sqrt n \rfloor$ elements in those arrays. The second array have between $n - \lfloor \sqrt n \rfloor$ to $n$ elements in range $\sqrt n$ to $n\sqrt n$ so using counting sort will run in $O(n\sqrt n)$. Using bucket sort where each bucket has all the elements in subrange with n integers each bucket can be sorted with counting sort in O(n) and there are $\sqrt n$ buckets so the sort will also take $O(n\sqrt n)$.
My problem is how to sort that second array in $O(n)$? I assume it is something to do with the amount of buckets or maybe the subrange of each bucket, as sorting the second array costs $O(number\_ of\_buckets * O(number\_of\_elements\_in\_bucket + number\_of\_integers\_in\_range))$