TADM2E 4.24

It's not clear to me if the first $ n - \sqrt n $ element being sorted means that the remaining $ \sqrt n $ elements are all bigger or not, but let's suppose they are not, since that's more general.

First sort the remaining $ \sqrt n $ elements in $ O(\sqrt n \log \sqrt n) $ time. After that we can do a simple merge step to merge the two sorted arrays in $ O(n) $ time. Since $ \sqrt n $ dominates $ \log \sqrt n $ we can come to the conclusion that the total running time of this algorithm is: $ O(\sqrt n \log \sqrt n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n) $