# sorting – 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 $$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:

1. elements smaller than $$sqrt n$$
2. element in range $$sqrt n$$ to $$nsqrt n$$
3. 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))$$