sort array with some of the elements in a known range 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))$
Using radix sort, the second subarray can be sorted in $\Theta(log_{b}(n\sqrt n)(n + b)$ where $b$ is the base with which the numbers are represented. If $n$ is chosen  as the base, radix sort sort the array in $\Theta(log_{n}(n\sqrt n)(n + n)) = \Theta(\frac{3}{2}(n + n)) = \Theta(n)$. Now all 3 subarrays can be sorted in $\Theta(n)$ thus the array is sorted in $\Theta(n)$