How to sort an array $A[1..n]$ where all but $\lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$, at $\Theta(n)$ time?
In the rest of the answer I will slightly abuse the notation by treating $A$ as a set. For simplicity I will also assume that the integers to sort are distinct, so that we are dealing with sets instead of multisets. This assumption is easy to remove.
Construct a min-heap $H^-$ and a max-heap $H^+$, each containing all elements in $A$. Extract the minimum  $\lfloor \sqrt{n} \rfloor$ times from $H^-$ and let $S^-$ be the set of the extracted elements.
Similarly, extract the maximum $\lfloor \sqrt{n} \rfloor$ times from $H^+$, and let $S^+$ be the set of the extracted elements. The overall time required so far is $O(n) + O(\sqrt{n} \log n) = O(n)$. (Notice also that $S^- \cap S^+ = \emptyset$ since $2 \lfloor \sqrt{n} \rfloor \le n$ for $n &gt; 1$).
Now you know that all the elements in $A \setminus (S^- \cup S^+)$ are integers between $0$ and $n^{3/2}$ (actually, between $\sqrt{n}$ and $n^{3/2}$, but this is irrelevant), and therefore can be sorted in time $O(n)$ using Radix sort (indeed, each integer in $S \setminus (S^- \cup S^+)$ has just two digits when written in base $n$).
Let $A'$ be the sorted version of $A \setminus (S^- \cup S^+)$.
To obtain a sorted version of $A$, we just need to insert the elements in $S^- \cup S^+$ into the right position of $A'$.
This can be done by first sorting $S^- \cup S^+$ in time $O(n)$ (any quadratic-time algorithm suffices since $|S^- \cup S^+| \le 2 \sqrt{n}$) and then merging the resulting sorted sequence with $A'$ a-la-Mergesort.