let $A$ be an array of n elements. We know that $n – lfloor sqrt n rfloor$ elements are integers in range $sqrt n$ to $nsqrt 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 $nsqrt n$
- element bigger than $nsqrt 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 $nsqrt n$ so using counting sort will run in $O(nsqrt 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(nsqrt 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))$