From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

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