# Difference between revisions of "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 n$ we can come to the conclusion that the total running time of this algorithm is: $O(\sqrt n \log n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n)$