# 4.35

Revision as of 18:30, 20 September 2020 by Algowikiadmin (talk | contribs) (Created page with "It's not clear to me if the first <math>n - \sqrt n</math> element being sorted means that the remaining <math>\sqrt n</math> elements are all bigger or not, but let's suppose...")

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

First sort the remaining elements in time. After that we can do a simple merge step to merge the two sorted arrays in time. Since dominates we can come to the conclusion that the total running time of this algorithm is:

Back to Chapter 4