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

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

• One thing that can work is to split the second parition into buckets such that bucket $B_i$ contains element between $i*\sqrt{n}$ and $(i+1)*\sqrt{n}$. Then you should be able to use counting sort in each bucket for an overall $O(n -\sqrt{n})$ cost by summing the individual sorting costs. P.S for efficient space to be in $O(n)$ and not $O(n\sqrt{n})$ you can note that each bucket has $\sqrt{n}$ different values you can simply 'renumber them' to be from $0,\ldots,\sqrt{n}-1$. – jjohn May 4 at 13:43
• @jjohn but if each bucket have $k_i$ elements and subrange of $\sqrt n$ elements then the count of sort of each bucket is done in $O(k_i + \sqrt n)$ there are n - 1 buckets so $\sum_{i=1}^{n - 1} O(k_i + \sqrt n) = \sum_{i=1}^{n - 1} O(k_i) + O(n\sqrt n)$ – CforLinux May 4 at 14:06
• Yes, you are absolutely right! – jjohn May 4 at 14:38
• I’m voting to close this question because OP solved it on their own. – Yuval Filmus May 4 at 17:17
• You can post your solution as answer and it is fine to do so, but editing question to provide solution yields dangling question, that is not good way to go at SE. – Evil May 6 at 3:17

First, do a linear scan to find all integer number in range $$[\sqrt{n},n\sqrt{n}]$$ and put those elements into array $$A'$$, and put $$\sqrt{n}$$ remaining elements into an array $$A^{''}$$. The running time of this linear scan of the array $$A$$ is $$\Theta(n)$$.
So by comparison based algorithm, such as merge sort, sort $$A^{''}$$ in $$\sqrt{n}\log \sqrt{n}$$.
Now by using Radix-Sort, you can sort $$A'$$ in linear time, if you set the base $$d=\log_x$$ to $$n$$ then the running time of radix-sort is $$\mathcal{O}\left(\frac{3}{2}\log_n n(n+n)\right)=\mathcal{O}(n).$$
So you have to merge two sorted arrays $$A',A^{''}$$ that can be merged in $$\mathcal{O}(n)$$. Consequently, overall running time is $$\mathcal{O}\left(\sqrt{n}\log \sqrt{n}+n\right)=\mathcal{O}(n)$$
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)$$