sort array with some of the elements in a known range

Question

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))$

Answer 1

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)$

Answer 2

It's possible to sort your array in linear time by using a method that use comparison based and non-comparison based sorting algorithms as subroutines.

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)$$