Sort an array in specific bounds
I am not sure counting sort would work, since it does not depend on the base, but on the range of the sorted values. In this case, you would need to create an array of size $(n-1)\sqrt{n}$ to count, so you would be in $\Omega(n^{3/2})$. As suggested in the comment, radix sort may do the trick here.

It is not possible to sort in $O(n)$ for one of the other bounds. Indeed, the problematic part would be sorting values not in the bounds $[\sqrt{n}, n\sqrt{n}]$: sorting $\frac{n}{2}$ values requires $\Omega(n\log n)$ time.
On the other hand, sorting $\frac{n}{\log n}$ values can be done in $O\left(\frac{n}{\log n}\log\left(\frac{n}{\log n}\right)\right) = O(n)$ time.