# Time complexity of sorting a partially sorted list

Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order.

How would you sort the whole list given the following:

a) $f(n)=O(1)$

b) $f(n)=O(\log n)$

c) $f(n)=O(n^{1/2})$

d) How big can $f(n)$ be for the list to remain sortable in $O(n)$ time?

I hope somebody can help, thanks in advance.

• Unless this was postively known to be a performance bottleneck, I would just throw the default library quicksort implementation at it and not worry further. – Henning Makholm Sep 30 '11 at 18:23
• @Henning: In other words, you're ignoring the question. – TonyK Sep 30 '11 at 20:24
• @Tony, he asked me how I would sort the various lists, and I answered truthfully to the best of my ability. – Henning Makholm Sep 30 '11 at 21:05
• @Henning: Well duh. In other other words, you're disparaging the question. So I just voted it up. – TonyK Sep 30 '11 at 21:07

You can sort the unordered elements in time $O(f(n) \log f(n))$, and then merge the two lists in time $O(\max (n, f(n)))$. So this gives you $O(n)$ as long as $f(n) \log f(n) = O(n)$, which I think answers d).
The trouble with a) is this: With a binary search, you can find the positions to insert the unordered elements in $O(\log n)$ time; but physically inserting them in the list takes $O(n)$ time, because you have to shift all those elements up by one. The same applies, mutatis mutandis, to b) and c).