4.35

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

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

Back to Chapter 4